六大排序算法比较

一、分类与性能总结

二、详细算法介绍

exchange代码

public static void exchange(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

1. 插入排序

1.1 算法思想

直接插入排序的核心思想就是： **将包括当前索引的左边都是有序的，将遍历到的元素插入已经排序元素中的适当位置。**默认首位为已排序，从第二个元素遍历，每个元素与前一个元素比较，如果小于前一个元素则与前一个元素交换位置。

1.2 代码实现

public static void insertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            //将a[i]插入到前面适当位置
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j-1]) {
                    exchange(a, j, j-1);
                }
            }
        }
    }

2. 希尔排序

2.1 算法思想

希尔排序的核心思想就是： 将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

2.2 代码实现

public static void shell(int[] a) {
        int gap = a.length/2;
        while (gap >= 1) {
            for (int i = gap; i < a.length; i++) {
                if(a[i]<a[i-gap]){
                    exchange(a, i, i-gap);
                }
            }
            gap = gap/2;
        }
    }

3. 选择排序

3.1 算法思想

简单选择排序的核心思想就是：比较+交换。
1. 从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

3.2 代码实现

public static void selection(int[] a) {
        for (int i = 0; i < a.length; i++) {//遍历每个位置
            int min = i;//最小元素的索引
            //寻找后方是否有最小元素 如果有交换索引
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            //找到了最小元素的索引后交换元素
            exchange(a, i, min);
        }
    }

4. 堆排序

4.1 算法思想

1. 构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
2. 将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。
3. 重新构建堆。
4. 重复2~3，直到待排序列中只剩下一个元素(堆顶元素)。

详细见：Java实现堆排序和图解

4.2 代码实现

5. 冒泡排序

5.1 算法思想

冒泡排序的思路比较简单，其核心思想为：
1. 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；
（ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
2. 对序列当中剩下的n-1个元素再次执行步骤1。
3. 对于长度为n的序列，一共需要执行n-1轮比较

设置交换标志flag，如果发生了交换则继续循环，未发生则跳出循环

5.2 代码实现

public static void bubble(int[] a) {
        for (int i = 0; i < a.length; i++) {//排序的次数（数组元素个数）
            for (int j = 0; j < a.length - i - 1; j++) {// a.length - i - 1其中-1是为了元素和后面对比时候不越界，-i是减去i个已经排序过
                if (a[j] > a[j + 1]) {
                    exchange(a, j, j + 1);
                }
            }
        }
    }

6. *快速排序

6.1 算法思想

快速排序的基本思想：找一个基准元素，将大于基准的元素放在基准左侧，小于基准的放在右侧这样完成了一次。再分别对基准的左右两侧做快速排序。利用双指针法会比较简单

详细见：快速排序（java实现）

6.2 代码实现

public static void quick(int[] a ,int low, int high) {
        if (low > high) {
            return;
        }
        int base = a[low];//选择一个基准
        //设置两个指针分别指向最左 和最右
        int i = low;
        int j = high;

        while (i < j) {
            //先看右边，指针往左寻找比base小的元素(比base大或相等的跳过)
            while (a[j]>=base && i<j){
                j--;
            }
            //再看左边，指针往右寻找比base大的元素(比base小或相等的跳过)
            while (a[i]<=base && i<j){
                i++;
            }
            //到这里有两种情况：1.i<j 这时a[i]>base a[j]<base ==》交换二者位置
            //                  2.i=j 即 i挪动到了j所指向的元素时还没找到比base大的  ==》将base与a[i]交换
            //                          或j挪动到了i所指元素还没找到比base小的
            if(i<j){//(情况1.)
                exchange(a, i, j);
            }
        }
        //(情况2.)此时i和j指针指向相同元素，基准与其交换位置
        a[low] = a[i];
        a[i] = base;
        //递归调用 快排base左侧
        sort(a,low,j-1);
        //递归调用 快排base右侧
        sort(a, j+1, high);

    }

参考博文：https://www.jianshu.com/p/be03d96848f7.