数据结构奇妙旅程之七大排序

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏：xiaoxie的JAVA系列专栏——CSDN博客●'ᴗ'σσணღ*
我的目标:"团团等我💪( ◡̀_◡́ ҂)"

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝+关注（互三必回）!

一.排序的概念

排序的概念

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

稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持

不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

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

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

二.插入排序

1.直接插入排序

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

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。

1.过程

假设我们有一个数组array{15，87，63，5，98，23，1，82，10} ；我们如果使用直接插入排序的过程如下：

原始： 15 87 63 5 98 23 1 82 10

第一趟： 15 87 63 5 98 23 1 82 10

第二趟： 15 87 63 5 98 23 1 82 10

第三趟：15 63 87 5 98 23 1 82 10

......

第n(9)趟: 1 5 10 15 23 63 82 87 98

2.代码

我们可以把他写为Java代码如下：

public class Sort {
    public static void insertSort(int[] array) {
        insert(array,0, array.length-1);
    }
    private static void insert(int[] array,int start,int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (;j >= start; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
}

C++版本如下

#include <iostream>
using namespace std;

class Sort {
public:
    static void insertSort(int array[], int size) {
        insert(array, 0, size-1);
    }

private:
    static void insert(int array[], int start, int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                if (array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
};

3.时间复杂度

最好情况下：

直接插入排序在最好情况下也就是在数据都有序的情况下为O（n)。

最坏情况下：

直接插入排序的最坏情况也就是在数据为逆序的情况下为O（n^2)。

4.空间复杂度

因为直接插入排序是在本数组中实现的没有借用辅助空间所以为O（1）。

5.稳定性

该算法为稳定的

值得注意的是元素集合越接近有序，直接插入排序算法的时间效率越高。

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

希尔排序法又称缩小增量法。希尔排序法的基本思想是：将待排序的数组按照一定的增量分组，对每个分组进行直接插入排序，然后逐步缩小增量，重复进行分组和直接插入排序的操作，直到增量缩小为1，最后进行最后一次直接插入排序。

1.过程

2.代码

java

public class Sort {
  
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            Shell(array,gap);
        }
    }
    private 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;
        }
    }
}

C++

#include <iostream>
using namespace std;

void shellSort(int array[], int size) {
    int gap = size;
    while (gap > 1) {
        gap /= 2;
        Shell(array, size, gap);
    }
}

void Shell(int array[], int size, int gap) {
    for (int i = gap; i < size; 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;
    }
}

3.时间复杂度

希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在不同的书中给出的希尔排序的时间复杂度都不固定

《数据结构 (C 语言版 ) 》 --- 严蔚敏

《数据结构-用面向对象方法与C++描述》--- 殷人昆

4.空间复杂度

因为希尔排序是直接插入排序的优化所以是在本数组中实现的没有借用辅助空间所以为O（1）。

5.稳定性

不稳定

6.希尔排序的特性

1. 希尔排序是对直接插入排序的优化。

2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

三.选择排序

3.直接选择排序

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

1.过程

1.在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

3.在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

2.代码

Java

public class Sort {
    public static void selectSort(int[] array) {
        select(array,0, array.length-1);
    }
    private static void select(int[] array,int start,int end) {
        for (int i = 0; i <= end ; i++) {
            int minIndex = i;
            for (int j = i+1; j <= end ; j++) {
                if(array[j] < array[minIndex]) {
                    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;
    }
}

C++

#include <iostream>
using namespace std;
void selectSort(int array[], int size) {
    select(array, 0, size - 1);
}

void select(int array[], int start, int end) {
    for (int i = 0; i <= end; i++) {
        int minIndex = i;
        for (int j = i + 1; j <= end; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        swap(array, i, minIndex);
    }
}

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

3.时间复杂度

最好情况和最坏情况都为：O（n^2） 所以不是很推荐使用

4.空间复杂度

因为直接选择排序是在本数组中实现的没有借用辅助空间所以为O（1）。

5.稳定性

不稳定

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

4.堆排序（需要重点掌握）

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

1.过程

2.代码

Java

private static void swap(int[]array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static  void heapSort(int[] array) {
        crateHeap(array);//首先创建大根堆
        int end = array.length-1;
        while (end >= 0) {
           swap(array,0,end);
           siftDown(array,0,end);
           end--;
        }
    }
    // 创建大根堆
    private static void crateHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            siftDown(array,parent,array.length);
        }
    }
    // 向下调整
    private static void siftDown(int[] array,int parent,int len) {
        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;
            }
        }
    }

C++

#include <iostream>
using namespace std;

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

void heapSort(int array[], int length) {
    createHeap(array, length); // 首先创建大根堆
    int end = length - 1;
    while (end >= 0) {
        swap(array, 0, end);
        siftDown(array, 0, end);
        end--;
    }
}

// 创建大根堆
void createHeap(int array[], int length) {
    for (int parent = (length - 2) / 2; parent >= 0; parent--) {
        siftDown(array, parent, length);
    }
}

// 向下调整
void siftDown(int array[], int parent, int len) {
    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;
        }
    }
}

3.时间复杂度

因为堆是一颗完全二叉树所以他的时间复杂度为：O（n*logN)。

4.空间复杂度

没有借助辅助空间所以空间复杂度为：O(1)。

5.稳定性

不稳定

四.交换排序

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

5.冒泡排序

1.过程

2.代码

Java

 private static void swap(int[]array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void bubbleSort(int[] array) {
        //10个元素遍历9趟
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            //没有交换就证明有序
            if(flag == false) {
                return;
            }
        }
    }

C++

#include <iostream>
using namespace std;

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

void bubbleSort(int array[], int length) {
    // 对于10个元素，遍历9趟
    for (int i = 0; i < length - 1; i++) {
        bool flag = false;
        for (int j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                flag = true;
            }
        }
        // 若没有交换发生，则证明数组已有序
        if (!flag) {
            return;
        }
    }
}

3.时间复杂度

最好情况下：

冒泡排序在最好情况下也就是在数据都有序的情况下为O（n)。

最坏情况下：

冒泡排序的最坏情况也就是在数据为逆序的情况下为O（n^2)。

4.空间复杂度

没有借助辅助空间所以空间复杂度为：O(1)。

5.稳定性

稳定

6.快速排序（重点掌握）

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

因为根据划分基准值的方法不同其过程也不一样，一般有Hoare法，挖坑法（常用）来划分基准值

1.1Hoare法过程

需要注意的是快速排序需要进行优化，防止出现像{1，2，3，4，5，6，7，8，9}这样的情况如果出现这种情况，二叉树会变成一颗斜树，降低排序速率这时候我们需要使用1 .三数取中法选基准值

如果 . 递归到小的子区间时，可以考虑使用插入排序 （这里就不优化了感兴趣的可以自己下去实现）

1.2Hoare法代码

  private static void swap(int[]array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void quickSort(int[] array) {
        quick(array,0, array.length-1);
    }

    private static void quick(int[] array,int left,int right) {
        if(right-left <= 1) {
            return;
        }
        //三数取中法
        int index = middleNum(array,left,right);
        swap(array,left,index);
        int pivot = partitionHoare(array,left,right);
        quick(array,left,pivot-1);//递归左边
        quick(array,pivot+1,right);//递归右边
    }
    //三数取中
    private static int middleNum(int[] array,int start,int end) {
        int mid = start+((end-start)>>1);
        if(array[start] <  array[end]) {
            if(array[mid] > array[end]) {
                return end;
            } else if (array[mid] < array[start]) {
                return start;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[end]) {
                return end;
            } else if (array[mid] > array[start]) {
                return start;
            }else {
                return mid;
            }
        }
    }
    //获取基准值的位置使用Hoare法
    private static int partitionHoare(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);
        return left;
    }

C++版本

#include <iostream>
using namespace std;

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

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

void quick(int array[], int left, int right) {
    if (right - left <= 1) {
        return;
    }
    // 三数取中法
    int index = middleNum(array, left, right);
    swap(array, left, index);
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1); // 递归左边
    quick(array, pivot + 1, right); // 递归右边
}

// 三数取中
int middleNum(int array[], int start, int end) {
    int mid = start + ((end - start) >> 1);
    if (array[start] < array[end]) {
        if (array[mid] > array[end]) {
            return end;
        } else if (array[mid] < array[start]) {
            return start;
        } else {
            return mid;
        }
    } else {
        if (array[mid] < array[end]) {
            return end;
        } else if (array[mid] > array[start]) {
            return start;
        } else {
            return mid;
        }
    }
}

// 获取基准值的位置使用Hoare法
int partitionHoare(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);
    return left;
}

2.1挖坑法过程（重点掌握）考试选择题过程一般使用挖坑法

2.2 挖坑法代码（重点掌握）

Java

 private static void swap(int[]array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void quickSort(int[] array) {
        quick(array,0, array.length-1);
    }

    private static void quick(int[] array,int left,int right) {
        if(right-left <= 1) {
            return;
        }
        //三数取中法
        int index = middleNum(array,left,right);
        swap(array,left,index);
        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);//递归左边
        quick(array,pivot+1,right);//递归右边
    }
    //三数取中
    private static int middleNum(int[] array,int start,int end) {
        int mid = start+((end-start)>>1);
        if(array[start] <  array[end]) {
            if(array[mid] > array[end]) {
                return end;
            } else if (array[mid] < array[start]) {
                return start;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[end]) {
                return end;
            } else if (array[mid] > array[start]) {
                return start;
            }else {
                return mid;
            }
        }
    }
    //获取基准值的位置使用挖坑法
    private 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;
    }

C++

#include <iostream>
using namespace std;

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

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

void quick(int array[], int left, int right) {
    if (right - left <= 1) {
        return;
    }
    // 三数取中法
    int index = middleNum(array, left, right);
    swap(array, left, index);
    int pivot = partition(array, left, right);
    quick(array, left, pivot - 1); // 递归左边
    quick(array, pivot + 1, right); // 递归右边
}

// 三数取中
int middleNum(int array[], int start, int end) {
    int mid = start + ((end - start) >> 1);
    if (array[start] < array[end]) {
        if (array[mid] > array[end]) {
            return end;
        } else if (array[mid] < array[start]) {
            return start;
        } else {
            return mid;
        }
    } else {
        if (array[mid] < array[end]) {
            return end;
        } else if (array[mid] > array[start]) {
            return start;
        } else {
            return mid;
        }
    }
}

// 获取基准值的位置使用挖坑法
int partition(int array[], int left, int right) {
    int pivot = array[left]; // 基准值
    while (left < right) {
        while (left < right && array[right] >= pivot) {
            right--;
        }
        array[left] = array[right];

        while (left < right && array[left] <= pivot) {
            left++;
        }
        array[right] = array[left];
    }
    array[left] = pivot; // 将基准值放入正确位置
    return left;
}

3.时间复杂度

最好情况下数据为无序的时候为O(n*logN)。

最坏情况下数据为有序或者是逆序的时候为O（n^2）。

4.空间复杂度

在递归调用过程中，需要使用O(log n)的栈空间来存储递归调用的上下文信息所以空间复杂度为：O(logN)。

5.稳定性

不稳定

7.归并排序（重点掌握）

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

1.过程

2.代码

Java

public static void mergeSort(int[] array) {
        mergeFunc(array,0,array.length-1);
    }
    private static void mergeFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = left + ((right-left) >> 1);
        //开始分解
        mergeFunc(array,left,mid);
        mergeFunc(array, mid+1, right);
        //开始合并
        merge(array,left,right,mid);
    }
    private static void merge(int[] array,int left,int right,int mid) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmp = new int[right-left+1];//创建一个临时数组来储存数据
        int k = 0;//临时数组下标
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        //看那个数组还有数据就拷贝过去
        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //3.拷贝到源数组
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

C++

#include <iostream>
using namespace std;

void mergeSort(int array[], int length) {
    mergeFunc(array, 0, length - 1);
}

void mergeFunc(int array[], int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + ((right - left) >> 1);
    // 开始分解
    mergeFunc(array, left, mid);
    mergeFunc(array, mid + 1, right);
    // 开始合并
    merge(array, left, right, mid);
}

void merge(int array[], int left, int right, int mid) {
    int s1 = left;
    int e1 = mid;
    int s2 = mid + 1;
    int e2 = right;
    int tmp[right - left + 1]; // 创建一个临时数组来储存数据
    int k = 0; // 临时数组下标

    while (s1 <= e1 && s2 <= e2) {
        if (array[s1] <= array[s2]) {
            tmp[k++] = array[s1++];
        } else {
            tmp[k++] = array[s2++];
        }
    }

    // 看那个数组还有数据就拷贝过去
    while (s1 <= e1) {
        tmp[k++] = array[s1++];
    }
    while (s2 <= e2) {
        tmp[k++] = array[s2++];
    }

    // 3.拷贝到源数组
    for (int i = 0; i < k; i++) {
        array[i + left] = tmp[i];
    }
}