【数据结构与算法】排序

一.排序的概念及引用
- 1.1 排序的概念
- 1.2 常见的排序算法
二.常见排序算法的实现
- 2.1 插入排序
- - 直接插入排序
  - 希尔排序( 缩小增量排序 )
- 2.2 选择排序
- - 直接选择排序
  - 堆排序
- 2.3 交换排序
- - 冒泡排序
  - 快速排序
  - 快速排序优化：
  - 非递归实现快速排序
- 2.4归并排序
- - 2.4.3 海量数据的排序问题
三.排序算法复杂度及稳定性分析
四.非基于比较排序

一.排序的概念及引用

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序

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

1.2 常见的排序算法

在这里插入图片描述

二.常见排序算法的实现

2.1 插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。类似于玩扑克牌

直接插入排序

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移

public static void insertSort(int[] array) {
    for(int i = 1;i < array.length;i++) {
        int tmp = array[i];
        int j = 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;
    }
}

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

时间复杂度：[对数据敏感]
最坏情况下：O(n^2) 逆序的
最好情况下：数据是有序的 O(n)
直接插入排序的使用场景是：当数据量小，并且已经趋于有序的时候，使用直接插入排序
空间复杂度：O(1)
稳定性：稳定的排序

希尔排序( 缩小增量排序 )

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

在这里插入图片描述

public static void shell(int[] array,int gap) {
    for(int i = gap ;i < array.length;i++) {
        int tmp = array[i];
        int j = i-gap;
        for (; j >= 0 ; j -= gap) {
            if(array[j] > tmp) {
                array[j+gap] = array[j];
            }else {
                break;
            }
        }
        array[j+gap] = tmp;
    }
}

public static void shellSort(int[] array) {
    int gap = array.length;
    while (gap > 1) {
        shell(array,gap);
        gap /= 2;
    }
    shell(array,1);
}

希尔排序的特性总结：

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

2.2 选择排序

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

直接选择排序

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if(array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        swap(array,minIndex,i);
    }
}

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

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

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

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

private static void shiftDown(int[] array,int root,int len) {
    int parent = root;
    int child = (2*parent) + 1;
    while (child < len) {
        if(child+1 < len && 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 createHeap(int[] array) {
    for (int p = (array.length-1-1)/2; p >= 0 ; p--) {
        shiftDown(array,p,array.length);
    }
}


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

堆排序的特性总结：

堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

2.3 交换排序

冒泡排序

public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j] > array[j+1]) {
                swap(array,j,j+1);
            }
        }
    }
}

优化一下代码让有序性的代码就不进行比较了

public static void bubbleSort2(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        boolean flg = false;
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j] > array[j+1]) {
                swap(array,j,j+1);
                flg = true;
            }
        }
        if(!flg) {
            break;
        }
    }
}

冒泡排序的特性总结：

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

快速排序

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

将区间按照基准值划分为左右两半部分的常见方式有：

Hoare版

public static void quickSort(int[] array) {
    quick(array,0,array.length-1);
}

private static void quick(int[] array,int left,int right) {
    if(left >= right) return;
    int pivot = partitionHoare(array,left,right);
    quick(array,left,pivot-1);
    quick(array,pivot+1,right);
}

private static int partitionHoare(int[] array,int low,int high) {
    int i = low;
    int tmp = array[low];
    while (low < high) {
        while (low < high && array[high] >= tmp) {
            high--;
        }
        //此时high就是你要找的数字
        while (low < high && array[low] <= tmp) {
            low++;
        }
        //此时low就是你要找的数字
        swap(array,low,high);
    }
    swap(array,low,i);
    return low;
}

挖坑法

private static int partitionHole(int[] array,int low,int high) {
    int tmp = array[low];
    while (low < high) {
        while (low < high && array[high] >= tmp) {
            high--;
        }
        array[low] = array[high];
        while (low < high && array[low] <= tmp) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = tmp;
    return low;
}

前后指针

方法一：

private static int partition1(int[] array,int low,int high) {
    int prev = low ;
    int cur = low+1;
    while (cur <= high) {
        if(array[cur] < array[low] && array[++prev] != array[cur]) {
            swap(array,cur,prev);
        }
        cur++;
    }
    swap(array,prev,low);
    return prev;
}

方法二：

private static int partition(int[] array, int left, int right) {
    int d = left + 1;
    int pivot = array[left];
    for (int i = left + 1; i <= right; i++) {
        if (array[i] < pivot) {
            swap(array, i, d);
            d++;
        }
    }
    swap(array, d - 1, left);
    return d - 1;
}

快速排序优化：

区间优化（插入排序）(不能解决递归深度问题)

public static void insertSortRange(int[] array,int low,int end) {
    for(int i = low+1;i <= end;i++) {
        int tmp = array[i];
        int j = i-1;
        for (; j >= low ; j--) {
            if(array[j] > tmp) {
                array[j+1] = array[j];
            }else {
                break;
            }
        }
        array[j+1] = tmp;
    }
}

private static void quick(int[] array,int left,int right) {
    if(left >= right) return;

    //1.在某个区间的时候进行优化(插入排序)(不能解决递归深度问题)
    if(right-left+1 <= 70000) {//这里值的大小看情况而定
        //进行插入排序：
        insertSortRange(array, left, right);
        return;
    }

    int pivot = partitionHoare(array,left,right);
    quick(array,left,pivot-1);
    quick(array,pivot+1,right);
}

三数取中法

public static int medianOfThreeIndex(int[] array, int left, int right){
    int mid = left + (right - left) >>> 1;
    if(array[left] < array[right]){
        if(array[mid] < array[left]){
            return left;
        }else if(array[mid] < array[right]){
            return mid;
        }else if(array[mid] > array[right]){
            return right;
        }
    }else {
        if(array[mid] < array[right]){
            return right;
        }else if(array[mid] > array[left]){
            return left;
        }else {
            return mid;
        }
    }
    return mid;
}

private static void quick(int[] array,int left,int right) {
    if(left >= right) return;

    //1.在某个区间的时候进行优化(插入排序)(不能解决递归深度问题)
    if(right-left+1 <= 70000) {//这里值的大小看情况而定
        //进行插入排序：
        insertSortRange(array, left, right);
        return;
    }

    //2.三数取中法
    int index = medianOfThreeIndex(array, left, right);
    swap(array,left,index);
    int pivot = partitionHoare(array,left,right);
    quick(array,left,pivot-1);
    quick(array,pivot+1,right);
}

非递归实现快速排序

public static void quickSortNor(int[] array) {
    Stack<Integer> stack = new Stack<>();
    int left = 0;
    int right = array.length-1;
    int piovt = partitionHole(array,left,right);
    //左边有两个数据及以上
    if(piovt > left+1){
        stack.push(left);
        stack.push(piovt-1);
    }
    if(piovt < right-1){
        stack.push(piovt+1);
        stack.push(right);
    }
    while (!stack.isEmpty()){
        right = stack.pop();
        left = stack.pop();

        piovt = partitionHole(array,left,right);
        //左边有两个数据及以上
        if(piovt > left+1){
            stack.push(left);
            stack.push(piovt-1);
        }
        if(piovt < right-1){
            stack.push(piovt+1);
            stack.push(right);
        }
    }
}

快速排序总结：

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

2.4归并排序

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

private static void merge(int[] array,int low,int mid,int high){
    int s1 = low;
    int e1 = mid;
    int s2 = mid+1;
    int e2 = high;
    int[] tmpArr = new int[high-low+1];
    int k = 0;//k代表tmpArr数组下标
    //证明两个段都是有数据的
    while (s1 < e1 && s2 < e2){
        if(array[s1] < array[s2]){
            tmpArr[k++] = array[s1++];
        }else {
            tmpArr[k++] = array[s2++];
        }
    }
    while (s1 < e1){
        tmpArr[k++] = array[s1++];
    }
    while (s2 < e2){
        tmpArr[k++] = array[s2++];
    }
    for (int i = 0; i < tmpArr.length;i++){
        array[i+low] = tmpArr[k];
    }
}

public static void mergeSortInternal(int[] array,int low,int high){
    if(low >= high) return;

    int mid = low + ((high-low) >>> 1);
    mergeSortInternal(array,low,mid);
    mergeSortInternal(array,mid+1, high);
    merge(array,low,mid,high);
}

public static void mergeSort(int[] array){
    mergeSortInternal(array,0,array.length-1);
}

非递归实现

public static void mergeSortNor(int[] array){
    int gap = 1;
    while (gap < array.length){
        for(int i = 0;i < array.length;i += 2*gap){
            int left = i;
            int mid = left+gap+1;
            //修正 mid
            if(mid >= array.length){
                mid = array.length - 1;
            }
            int right = mid + gap;
            //修正right
            if(right >= array.length){
                right = array.length - 1;
            }
            merge(array,left,mid,right);
        }
        gap *= 2;
    }
}

归并排序总结：

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

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

先把文件切分成 200 份，每个 512 M
分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

三.排序算法复杂度及稳定性分析

在这里插入图片描述

四.非基于比较排序

计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中

public static void countSort(int[] array){
    //1.获取最大值和最小值
    int maxVal = array[0];
    int minVal = array[0];
    for (int i = 0; i < array.length; i++) {
        if(array[i] < minVal){
            minVal = array[i];
        }
        if(array[i] > maxVal){
            maxVal = array[i];
        }
    }
    //2.开始计数
    int range = maxVal - minVal +1;
    int[] count = new int[range];
    for (int i = 0; i < array.length; i++) {
        count[array[i]-minVal]++;
    }
    //3.遍历这个计数数组，把数据返回给 array
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0){
            array[index++] = i + minVal;
            count[i]--;
        }
    }
}