排序（数据结构系列13）网站首页 学无止境

这次小编与大家分享七大排序算法，其中的主要排序分为插入排序、选择排序、交换排序和归并排序四大类，所谓排序就是是一串记录，按照其中的某个或者是某些关键字的大小，递增或递减的排列起来的操作，其中会引入一个概念叫排序的稳定性，什么是稳定性呢？假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原来的序列中，r[i] = r[j],且r[i] 在r[j]之前，而在排序之后的序列中依旧保持r[i]在r[j]之前，那就说明该排序就一中稳定的排序算法，否则就是不稳定的。好了接下来我们通过在给大家介绍这些写排序算法的时候会给大家一一说明该算法是不是一个稳定的排序算法，大家通过这些算法来更好的了解一下稳定性的概念。

排序算法的引言：

排序分为两种：内部排序和外部排序。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动的数据的排序。

排序算法图：
接下来小编就给大家一一介绍一下各个排序算法吧！

1.插入排序

1.1直接插入排序

基本思想：

直接插入排序是一种简单的插入排序算法，其基本思想是把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序数列中，直到所有的记录插完为止，得到一个有序的序列，大家可以类比我们现实生活当中玩扑克牌时接扑克牌的情景。

前三次排序示意图：

代码实现如下所示：

package 排序算法.插入排序;
import java.util.Arrays;
//直接插入排序
public class Direct_Insertion_Sort {
    public static void insetSort(int[] array) {
        //一张牌的时候一定是有序的，所以我们直接从1开始
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//相当于要插入的值
            int j = i - 1;//与i - 1之前的所有元素进行比较
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    //array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
    public static void main(String[] args) {
        int[] array = {2,4,1,5,3,9,7,6,8};
        insetSort(array);
        System.out.println(Arrays.toString(array));
    }
}

结果如下所示：

直接插入排序的特性总结：

元素越接近有序，直接插入排序的时间效率就越高。
时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：稳定。
一般使用场景：数据基本有序时，建议使用直接插入排序。

注意：

其中如果这个排序算法是稳定的，那么就可以实现为不稳定的，但是如果一个排序算法本身就是不稳定的，那么就没有办法将其实现为稳定的。

1.2希尔排序

基本思想：

希尔排序又称为缩小增量法，希尔排序的基本思想是，先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为一样记录分在同一个组内，并对每一组内的记录进行排序，然后重复上述分组和排序的工作，当达到距离=1时，所有记录在统一组内进行排序。

希尔排序示意图：

代码如下所示：

package 排序算法.插入排序;
//希尔排序：
import java.util.Arrays;

public class ShellSort {
    public static void shellSort(int[] array) {
        int gap = array.length;//进行分组
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        //gap < 1的时候整体排序
        shell(array,1);
    }

    //给每组进行插入排序
    public static void shell(int[] array, int gap) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//相当于要插入的值
            int j = i - gap;//与i - 1之前的所有元素进行比较
            for (; j >= 0; j-= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                }else {
                    //array[j + 1] = tmp;
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {2,4,1,5,3,9,7,6,8};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}

结果如下所示:

直接插入排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序，当gap = 1时，数组已经接近有序了，这样就会很快，这样对于整体而言，可以达到优化的效果，我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法有很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定但是我们一般记它的时间复杂度为O(N^1.3)。
时间复杂度：O(N^1.3)。
空间复杂度：O(1)。
稳定性：不稳定。

2.选择排序

2.1直接选择排序

基本思想：

每一次从待排序的数据元素当中选出最小或者最大的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序的图示：

代码如下所示：

package 排序算法.选择排序;

import java.util.Arrays;

public class SelectSort {
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //寻找最小值
            int minIndex = i;
            int j = i + 1;
            for (; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void main(String[] args) {
        int[] array = {2,4,1,5,3,9,7,6,8};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }
}

结果如下所示：

直接选择排序的特性总结：

直接排序算法思考非常好理解，但是效率不高，实际中很少使用。
时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：不稳定。

2.2堆排序

基本思想：

堆排序是指利用堆积树这种数据结构设计的一种排序算法，他是选择排序的一种，他是通过堆来进行选择排序数据，需要注意的是，排升序的时候需要建大跟堆，排降序的时候需要建小根堆。

堆排序的示意图：

代码如下所示：

package 排序算法.选择排序;

import java.util.Arrays;

public class HeapSort {
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    private static void shiftDown(int[] array, int parent, int length) {
        int child = 2 * parent + 1;
        while (child < length) {
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {4,1,6,5,8,9,7,3,10,2};
        System.out.println("堆排序前的数组：" + Arrays.toString(array));
        heapSort(array);
        System.out.println("堆排序后的数组：" + Arrays.toString(array));
    }
}

结果如下所示：

堆排序的特性总结：

时间复杂度：O(N*logN)。
空间复杂度：O(1)。
稳定性：不稳定。

3.交换排序

3.1冒泡排序

基本思想：

交换排序的基本思想是：所谓交换，就是根据序列中两个记录键值的比较结果来对交换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录或者是较小的记录向后移动，键值较小的记录或者是较大的记录序列向前移动。

冒泡排序示意图：

代码如下所示：

package 排序算法.交换排序;

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (array[i] < array[j]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
    public static void main(String[] args) {
        int[] array = {4,1,6,5,8,9,7,3,10,2};
        bubbleSort(array);
    }
}

结果如下所示：

冒泡排序特性总结：

时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：稳定。

3.2快速排序

基本思想：

任取待排序元素序列中的某个元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应的位置上为止。

快速排序有三个版本：Hoare版、挖坑法和前后指针法。

3.2.1Hoare版

基本思想：
①右边找到比基准值小的停下来。

②左边找到比基准值大的停下来。

③将刚刚找到的左右两边的值进行交换。

Hoare版快速排序示意图：

代码如下所示：

package 排序算法.交换排序;

import java.util.Arrays;

public class HoareQuickSort {
    public static void quickSort(int[] array) {
        quick(array,0,array.length - 1);
        System.out.println("Hoare版快速排序后的数组：" + Arrays.toString(array));
    }
    //排序的函数
    public static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }
    //找基准值
    public static int partition(int[] array, int left, int right) {
       int tmp = array[left];
       int i = left;//记录基准值的下标
       while (left < right) {
           //右边找比基准值小的值停下来
           while (left < right && array[right] >= tmp) {
               right--;
           }
           //左边找比基准值大的值停下来
           while (left < right && array[left] <= tmp) {
               left++;
           }
           swap(array,left,right);
       }
       swap(array,left,i);//将当前的left的值和i下标的值进行交换
       return left;
    }

    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {4,1,6,5,8,9,7,3,10,2};
        System.out.println("Hoare版快速排序前的数组：" + Arrays.toString(array));
        quickSort(array);
    }
}

结果如下所示：

3.2.2挖坑法

基本思想：

①找一个基准值放到tmp中。

②右边找到比基准值小的，将其放入坑中。

③左边找到比基准值大的，将其放入坑中。

④最后将tmp里面的值放入到坑中。

挖坑法快速排序示意图：

以一趟排序为例，后面的递归即可！！！

代码如下所示：

package 排序算法.交换排序;

import java.util.Arrays;

//挖坑法
public class quickSort {
    public static void quick_sort(int[] array) {
        quick(array, 0, array.length - 1);
        System.out.println("挖坑快速排序后：" + Arrays.toString(array));
    }
    //进行排序
    public static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }
    //找基准
    public static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    public static void main(String[] args) {
        int[] array = {4,1,6,5,8,9,7,3,10,2};
        System.out.println("挖坑快速排序前：" + Arrays.toString(array));
        quick_sort(array);
    }
}

结果如下所示：

3.2.3前后指针法

基本思想：

①定义连个指针prev和cur。

②cur去找比基准值小的位置。

③将prev的下一个值与cur进行交换。前提是prev的下一个值与cur的值不相等。

④最后还完之后将prev的值与left的值进行交换。

前后指针排序示意图：

代码如下所示：

package 排序算法.交换排序;

import java.util.Arrays;

//前后指针法
public class QuickSortPointer {
    public static void QuickSortPointer(int[] array) {
        quickSort(array, 0, array.length - 1);
    }
    public static void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(array,start,end);
        quickSort(array, start, pivot - 1);
        quickSort(array, pivot + 1, end);
    }
    //基准划分
    public static int partition(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }

    private static void swap(int[] array, int cur, int prev) {
        int tmp = array[cur];
        array[cur] = array[prev];
        array[prev] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {4,1,6,5,8,9,7,3,10,2};
        System.out.println("前后指针排序前：" + Arrays.toString(array));
        QuickSortPointer(array);
        System.out.println("前后指针排序后：" + Arrays.toString(array));
    }
}

结果如下所示：

快速排序特性总结：

快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序。
时间复杂度：O(N*logN)这个是最好情况下的时间复杂度，最坏时间复杂度的是O(N^2)。
空间复杂度：O(logN)是最好情况下的空间复杂度，最坏情况下的空间复杂度是O(N)。
稳定性：不稳定。

4.归并排序

基本思想：

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列，即先是每一个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为二路归并。

归并排序的示意图：

代码如下所示：

package 排序算法.归并排序;

import java.util.ArrayList;
import java.util.Arrays;

//归并排序
public class mergeSort {
    public static void mereSort(int[] array) {
        mergeSortFunc(array,0,array.length - 1);
    }

    public static void mergeSortFunc(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        //分别递归左右子树，分解
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid + 1, right);
        //合并
        merge(array,left,right,mid);
    }
    private static void merge(int[] array, int start, int end, int mid) {
        int s1 = start;
//        int e1 = mid;
        int s2 = mid + 1;
//        int e2 = end;
        //申请一个数组
        int[] tmp = new int[end - start + 1];
        int k = 0;//表示tmp数组的下标。
        //用s1和s2进行比较,放入到tmp数组中
        while (s1 <= mid && s2 <= end) {
            if (array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
//                k++;
//                s2++;
            }
        }
        //判断两个数组中的元素是否都结束了
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }
        //tmp排完后的值拷贝的数组中
        for (int i = 0; i < tmp.length; i++) {
            array[i + start] = tmp[i];
        }
    }
    public static void main(String[] args) {
        int[] array = {4,1,6,5,8,9,7,3,10,2};
        System.out.println("归并排序前的数组：" + Arrays.toString(array));
        mereSort(array);
        System.out.println("归并排序后的数组：" + Arrays.toString(array));
    }
}

结果如下所示：

归并排序特性总结：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)。
空间复杂度：O(N)。
稳定性：稳定。

5.排序总结

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(N)	O(N^2)	O(N^2)	O(1)	稳定
插入排序	O(N)	O(N^2)	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
希尔排序		O(N^1.3)		O(1)	不稳定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不稳定
快速排序	O(N*logN)	O(N*logN)	O(N^2)	O(logN)~O(N)	不稳定
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(N)	稳定