Fork me on GitHub

经典排序

发表于
排序种类 最优时间复杂度 平均时间复杂度 最坏时间复杂度 稳定性
快速排序 nlogn nlogn n^2 稳定
冒泡排序 n n^2 n^2 稳定
插入排序 n n^2 n^2 稳定
归并排序 n nlogn nlogn 稳定
选择排序 n^2 n^2 n^2 不稳定
希尔排序 n nlog^2n 不稳定
堆排序 nlogn nlogn nlogn 不稳定

稳定性判断

如果在一个待排序的序列中，存在2个相等的数，在排序后这2个数的相对位置保持不变，那么该排序算法是稳定的；否则是不稳定的。

冒泡排序

基本思想

  • 比较相邻的元素。 如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
  • 在这一点，最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

通俗理解：冒泡就是生活中理解的冒泡，一个数与它相邻的数进行比较，从下往上遍历一次之后最下面的数就是最大的，再次遍历时从倒数第二个开始遍历，依次进行下去…

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class MaoPao {
    public static void main(String[] args) {
        int[] unSort = {2,5,6,4,1,3,8,7,9};
        int min;
        for (int i= unSort.length-1;i>=0;i--){
            for (int j=0;j<i;j++){
                if (unSort[j]>unSort[j+1]){
                    int temp = unSort[j];
                    unSort[j] = unSort[j+1];
                    unSort[j+1] = temp;
                }
            }
        }

        for (int anUnSort : unSort) {
            System.out.print(anUnSort + " ");
        }
    }
}

选择排序

基本思想

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
  • 然后，再从剩余未排序元素中继续寻找最小（大）元素，
  • 然后放到已排序序列的末尾。
  • 以此类推，直到所有元素均排序完毕。

通俗理解：两次for循环，外循环与内循环中的全部比较选出最大或最小

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class SelectorSort {
    public static void main(String[] args) {
        int[] unSort = {2,5,6,4,1,3,8,7,9};
        for (int i=0;i < unSort.length;i++){
            for (int j = i+1;j<unSort.length;j++){
                if (unSort[i]>unSort[j]){
                    int temp = unSort[i];
                    unSort[i] = unSort[j];
                    unSort[j] = temp;
                }
            }
        }
        for (int anUnSort : unSort) {
            System.out.print(anUnSort + " ");
        }
    }
}

插入排序

基本思想

  • 从第一个元素开始，该元素可以认为已经被排序
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于取出的元素，将该元素移到下一位置
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后
  • 重复步骤2~5

通俗理解：顺序排队中进行插队的行为

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class InsertSort {
    public static void main(String[] args) {
        int[] unSort = {2,5,6,4,1,3,8,7,9};
        for (int i=0;i<unSort.length-1;i++){
            for (int j=0;j<=i;j++){
                if (unSort[i+1]<unSort[j]){
                    int temp = unSort[i+1];
                    unSort[i+1] = unSort[j];
                    unSort[j] = temp;
                }
            }
        }

        for (int anUnSort : unSort) {
            System.out.print(anUnSort + " ");
        }
    }
}

希尔排序

基本思想

  • 确定步长
  • 在步长内进行排序
  • 缩小步长，进行排序
  • 直至步长为1

通俗理解：确定步长为x，依次比较0,0+x,0+2x….,1,1+x,2+x….再次缩小步长直至为1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ShellSort {
    public static void main(String[] args) {
        int[] unSort = {2,5,6,4,1,3,8,7,9};
        int gap =1,len = unSort.length;
        while (gap<len/3){
            gap = gap * 3 +1;
        }
        for (; gap>0; gap/=3){
            for (int i=gap;i<len;i++){
                for (int j=i-gap;j>=0 && unSort[j]>unSort[j+gap];j-=gap){
                    int temp = unSort[j];
                    unSort[j] = unSort[j+gap];
                    unSort[j+gap] = temp;
                }
            }
        }

        for (int anUnSort : unSort) {
            System.out.print(anUnSort + " ");
        }
    }
}

归并排序

基本思想

  • 先递归
  • 后合并

通俗理解：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class MergeSort {

    public static void main(String[] args) {
        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        mergeSort(a, 0, a.length - 1);
        System.out.println("排序结果：" + Arrays.toString(a));
    }

    private static void mergeSort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSort(a, low, mid);
            // 右边
            mergeSort(a, mid + 1, high);
            // 左右归并
            merge(a, low, mid, high);
            System.out.println(Arrays.toString(a));
        }
    }
    
    private static void merge(int[] a, int low, int mid, int high) {

        //辅助数组
        int[] temp = new int[high - low + 1];
        // 左指针
        int i = low;
        // 右指针
        int j = mid + 1;
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        System.arraycopy(temp, 0, a, 0 + low, temp.length);
    }
}

快速排序

基本思想

  • 从数列中挑出一个元素，称为”基准”（pivot），
  • 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  • 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class QuickSort {
    public static void main(String[] args) {

        int[] unSort = {2,5,6,4,1,3,8,7,9};
        int low = 0,high = unSort.length-1;
        int[] nums = qSort(unSort,low,high);
        for (int anUnSort : nums) {
            System.out.print(anUnSort + " ");
        }
    }

    private static int[] qSort(int[] unSort, int low, int high) {

        int flag = unSort[low];
        int i= low,j= high;
        while (i <= j){
            while (unSort[i] < flag){
                i++;
            }
            while (unSort[j] > flag){
                j--;
            }
            if (i <= j){
                int temp = unSort[i];
                unSort[i] = unSort[j];
                unSort[j] = temp;
                i++;
                j--;
            }
        }

//        for (int anUnSort : unSort) {
//            System.out.print(anUnSort + " ");
//        }
//        System.out.println();

        if (low < j){
            qSort(unSort,low,j);
        }
        if (i<high){
            qSort(unSort,i,high);
        }
        return unSort;
    }
}

堆排序

基本思想

  • 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
  • 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class HeapSort {

    public static void main(String[] args) {

        int[] unSort = {2, 5, 6, 4, 1, 3, 8, 7, 9};
        //进行对堆调整
        heapSort(unSort,unSort.length);
        for (int anUnSort : unSort) {
            System.out.print(anUnSort + " ");
        }
    }

    private static void heapSort(int[] unSort, int length) {

        int len = length-1;
        //找出最大值，并置于堆顶
        for (int i = len/2-1;i >= 0;i--){
            heapAdjust(unSort,i,len);
        }

        //最大值已排序
        while (len >= 0){
            swap(unSort,0,len);
            len--;
            heapAdjust(unSort,0,len);
        }
    }

    private static void heapAdjust(int[] unSort, int i, int length) {

        int left,right,j;
        while ((left = i*2+1) <= length){
            right = left+1;
            j=left;
            if(j < length && unSort[right] > unSort[left]){
                j++;
            }
            if (unSort[i] < unSort[j]){
                swap(unSort,j,i);
            }else {
                break;
            }
            i=j;
        }
    }

    private static void swap(int[] unSort,int min, int max) {
        int temp = unSort[min];
        unSort[min] = unSort[max];
        unSort[max] = temp;
        for (int anUnSort : unSort) {
            System.out.print(anUnSort + " ");
        }
        System.out.println();
    }
}