黑马程序员技术交流社区

标题: 三个小小排序 [打印本页]

---

作者: as803956087    时间: 2018-10-9 09:41
标题: 三个小小排序

冒泡排序：冒泡排序的思想就是从左到右循环判断两个相邻元素的大小，如果后一个元素的值小于前一个元素，则交换位置，一轮循环后最大值则在最右边，不过下一次循环，需要将最后一个最大值排除掉再进行循环。

public static int[] popSort(int[]a) {
    for (int i = 0; i < a.length; i++){
        for (int j = 0; j < a.length -i - 1; j++) {//因为每轮循环都要将最大值排除，所以j<a.length-i,再因为a[j]和a[j+1]作比较,j<a.length-i-1,避免越界。
            if (a[j] > a[j + 1]) {//判断前后两个数大小，用临时变量替换。
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    return a;
}
选择排序：第一次通过循环遍历数组，找到最小的元素与数组的第一个元素交换位置，第二次循环遍历数组找到第二小的元素与数组的第二个元素交换位置，以此类推。每轮循环找到最小的元素并交换位置后，下次遍历时应该避开这个最小元素。
public static int[]selectSort(int[] a) {
    for (int i = 0; i < a.length; i++){
        int min = a;//假设每轮循环第一个都是最小值
        int flag = i;//用于储存最小值下标
        for (int j = i + 1; j <a.length; j++) {//排除每轮循环的第i个值
            if (min > a[j]) {//判断第i个数是不是最小值，不是则交换
                min = a[j];
                flag = j;
            }
        }
        if (flag != i) {//如果flag不等于最初值，则说明第一个数不是最小值，两者交换
            a[flag] = a;
            a = min;
        }
    }
    return a;
}
插入排序：假定第一个元素为最小元素，判定第二个元素与第一元素的大小，如果第二个小于第一个，则交换位置，这时候第一个和第二个已经排好序，通过第三个元素与前面已经排好的第二个元素进行比较，如果大于第二个，则进行下一轮循环、否则交换位置后继续与第一个元素进行比较，外部控制循环直到到达数组末尾。
public static int[]insertSort(int[] a) {
    for (int i = 1; i < a.length; i++){
        int temp = a;//保存当前将要用于插入的值
        int j = i - 1;//用于遍历已经排好序的子集的下标
        if (temp < a[j]) {//判断子集的最大值与当前的值的大小，如果当前值大，则不需要循环
            while (j >= 0 &&a[j] > temp) {//如果子集的元素大于当前值，则修改当前值的位置
                a[j + 1] = a[j];//将j的位置的值向前移动,用于存放当前值
                j--;
            }
            a[j + 1] = temp;//循环结束后子集中所有大于temp的值都向前移动了一步，这时候j+1的位置就是temp应该插入的位置
        }
    }
    return a;
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2