2.01_十大排序算法

基本概念

稳定性

如果相等的2个元素、在排序前后的相对位置保持不变，那么这是稳定的排序算法

原地算法

不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入，空间复杂度为O(1)的都可以认为是原地算法

一、冒泡排序

• 步骤一：从头开始比较相邻的元素，如果第一个比第二个大，就交换它们两个；
• 经过一轮之后，最后一个元素就是最大的元素
• 步骤二：忽略步骤一找到的最大的元素，重复执行步骤一，直到全部元素有序

简单实现：

void bubbleSort(int *arr,int length){

    for (int end = length - 1; end >0;end--){
        for (int begin = 1; begin<=end; begin++) {
            if (arr[begin]<arr[begin-1]) {
                int tmp = arr[begin];
                arr[begin] = arr[begin-1];
                arr[begin-1] = tmp;
            }
        }
    }
}

冒泡排序优化版1

如果序列已经完全有序，可以提前终止冒泡排序。

void bubbleSort2(int *arr,int length){
    
    for (int end = length - 1; end >0;end--){
        bool sorted = true;
        for (int begin = 1; begin<=end; begin++) {
            if (arr[begin]<arr[begin-1]) {
                int tmp = arr[begin];
                arr[begin] = arr[begin-1];
                arr[begin-1] = tmp;
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

冒泡排序优化版2

如果序列已经局部有序，可以记录最后一次交换的位置，减少比较次数

void bubbleSort3(int *arr,int length){
    for (int end = length - 1; end>0; end--){
        int sortedIndex = 1;
        for (int begin = 1; begin<=end; begin++) {
            if (arr[begin]<arr[begin-1]) {
                int tmp = arr[begin];
                arr[begin] = arr[begin-1];
                arr[begin-1] = tmp;
                sortedIndex = begin;
            }
        }
        end = sortedIndex;
    }
}

冒泡排序性质

• 稳定性：稳定排序
• 空间复杂度：O(1)，属于原地算法
• 时间复杂度：最好时间复杂度：O(n)；最坏、平均时间复杂度O(n^2)

二、选择排序：

步骤一：从序列中找出最大的元素，然后与最末尾的元素交换位置
执行完一轮后，最末尾的那个元素就是最大的元素
步骤二：忽略曾经找到的最大元素，重复步骤一

void selectSort(int *arr,int length){
    
    for (int end = length - 1; end>0; end--){
        int maxIndex = 0;
        for (int begin = 1; begin<=end; begin++) {
            // 这里就算是 <= 也是不稳定排序例如下面这组数据
            // 7 5 10 10 2 4 2
            // 7 5 10 2  2 4 10
            // 排序一次之后位于序列尾部的2被插入到index = 3 的位置
            if (arr[maxIndex] < arr[begin]) {
                maxIndex = begin;
            }
        }
         int tmp = arr[end];
         arr[end] = arr[maxIndex];
         arr[maxIndex] = tmp;
    }
}

选择排序的性质

选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序

• 稳定性：不稳定排序
• 空间复杂度：O(1)，属于原地算法
• 时间复杂度：最好、最坏、平均时间复杂度都是O(n^2)

三、堆排序

堆排序可以认为是对选择排序的一种优化

• 步骤一：对序列进行原地建堆（heapify）
• 步骤二：重复执行以下操作，直到堆的元素数量为1
  2.1. 交换堆顶元素与尾元素
  2.2. 堆的元素数量减1
  2.3. 对0位置进行1次siftDown操作

void siftDown(int *arr,int index,int heapSize)
{
    int v = arr[index];
    // 第一个叶子节点的下标
    int half = heapSize >> 1;
    // 非叶子节点才需要下滤
    while (index < half) {
        // 取出左子节点的下标
        int childIndex = (index << 1) + 1;
        // 取出左子节点的值
        int child = arr[childIndex];
        // 取出右子节点的下标
        int rightIndex = childIndex + 1;
        //右子节点存在 并且 右子节点的值大于左子节点
        if (rightIndex < heapSize && arr[rightIndex] > child) {
            childIndex = rightIndex;
            child = arr[rightIndex];
        }
        
        // 如果 父节点的值大于最大子节点，不需要下滤，直接跳出循环
        if (v >= child) break;
        
        // 否则 用最大子节点的值覆盖父节点
        arr[index] = child;
        index = childIndex;
    }
    
    arr[index] = v;
    
}

void HeapSort(int *arr,int len)
{
    //原地建堆 采取自下而上的下滤
    for (int i = (len>>1) - 1;i>=0;i--){
        siftDown(arr,i,len);
    }
    
    int heapSize = len;
    while (heapSize>1) {
        // 堆顶元素和堆尾元素交换位置
        int tmp = arr[heapSize -1];
        arr[heapSize - 1] = arr[0];
        arr[0] = tmp;
        // 堆数组长度减1
        heapSize--;
        // 下滤，维护堆的性质
        siftDown(arr, 0, heapSize);
    }
}

堆排序的性质

• 稳定性：不稳定排序
• 空间复杂度：O(1)
• 时间复杂度：最好、最坏、平均时间复杂度：O(nlogn)

四、插入排序

1. 在执行过程中，插入排序会将序列分为2部分
   头部是已经排好序的，尾部是待排序的
2. 从头开始扫描每一个元素
3. 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序。

简单实现：

void InsertionSort(int *arr,int length)
{
    for(int begin = 1; begin<length; begin++){
        int cur = begin;
        while (cur>0 && arr[cur] < arr[cur-1]) {
            int tmp = arr[cur];
            arr[cur] = arr[cur-1];
            arr[cur-1] = tmp;
            cur--;
        }
    }
}

插入排序优化1

将交换转为挪动

1. 先将待插入的元素备份
2. 头部有序数据中比待插入元素大的，都朝尾部方向挪动一个位置
3. 将待插入元素放到最终合适的位置

for(int begin = 1; begin<length; begin++){
        int cur = begin;
        int v = arr[cur];
        while (cur>0 && v < arr[cur-1]) {
            arr[cur] = arr[cur-1];
            cur--;
        }
        arr[cur] = v;
    }

插入排序优化2

二分搜索优化

void InsertionSort(int *arr,int len){
    for (int i = 1; i<len; i++) {
        
        int v = arr[i];
        
        //二分查找 v 的插入位置
        int begin = 0;
        int end = i;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (v < arr[mid]) {
                end = mid;
            }else{
                begin = mid + 1;
            }
        }
        
        //跳出循环之后begin就是v的插入位置
        for (int j = i; j>begin; j--) {
            arr[j] = arr[j-1];
        }
        arr[begin] = v;
    }
}

插入排序的性质

• 稳定性：稳定排序
• 时间复杂度：最好时间复杂度: O(n)；最坏、平均时间复杂度：O(n^2)
  插入排序的时间复杂度与你序对的数量成正比关系，你序对的数量越多，插入排序的时间复杂度越高
• 空间复杂度：O(1)

注意

使用了二分搜索后，只是减少了比较次数，但是插入排序的平均时间复杂度依然是O(n^2)

五、归并排序（Merge Sort）

执行流程

• 不断地将当前序列平均分割成2个子序列，直到不能再分割
• 不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列

void merge(int *arr,int begin,int mid,int end)
{
    // 拷贝左边数组
    int left[mid - begin];
    for (int i = 0; i<(mid - begin); i++) {
        left[i] = arr[i + begin];
    }
    
    int li = 0,le = mid - begin;
    int ri = mid,re = end;
    int ai = begin;
    
    // 当左边数组全部移到正确的位置，排序完成
    while (li<le) {
        // 右边数组未排序完成 并且 ri位置的值小于li位置
        if (ri < re && arr[ri] < left[li]) {
            // 将 ri位置的值赋值给ai，ri++ ，ai++
            arr[ai++] = arr[ri++];
        }else{
            // 将li位置的值赋值给ai，li++，ai++
            arr[ai++] = left[li++];
        }
    }
}

void sort(int *arr,int begin,int end)
{
    if ((end - begin) < 2) return;
    int mid = (end + begin) >> 1;
    sort(arr, begin, mid);
    sort(arr, mid, end);
    merge(arr,begin,mid,end);
}

void MergeSort(int *arr,int len)
{
    sort(arr,0,len);
}

归并排序的性质

• 稳定性：稳定排序
• 空间复杂度：O(n/2 + logn) = O(n)
• 时间复杂度：最好、最坏、平均时间复杂度都是O(nlogn)

六、快速排序（Quick Sort）

执行流程

• 步骤一 ：从序列中选择一个轴点元素（假设每次选择0位置的元素为轴点元素）
• 步骤二：利用pivot将序列分割成2个子序列
  • 将小于pivot的元素放在pivot前面（左侧）
  • 将大于pivot的元素放在pivot后面（右侧）
  • 等于pivot的元素放在哪边都可以
• 步骤三：对子序列进行步骤一和步骤二操作，直到不能再分割（子序列中只剩下一个元素）

快速排序的本质

逐渐将每一个元素都转换为轴点元素

int pivotIndex(int *arr,int begin,int end)
{
    int pivot = arr[begin];
    end--;
    while (begin < end) {
        while (begin < end) {
            if (arr[end] <= pivot) {
                arr[begin] = arr[end];
                begin++;
                break;
            }else{
                end--;
            }
        }
        
        while (begin < end) {
            if (arr[begin] >= pivot) {
                arr[end] = arr[begin];
                end--;
                break;
            }else{
                begin++;
            }
        }
    }
    arr[begin] = pivot;
    return begin;
}

void sort(int *arr,int begin,int end)
{
    if ((end - begin) < 2) return;
    int mid = pivotIndex(arr, begin, end);
    sort(arr, begin, mid);
    sort(arr, mid + 1, end);
}

void QuickSort(int *arr,int length){
    sort(arr,0,length);
}

快速排序性质

• 稳定性：不稳定排序
• 空间复杂度：O(logn)
• 时间复杂度：最好、平均时间复杂度：O(nlogn)，最坏时间复杂度：O(n^2)
  为了降低最坏情况出现的概率，一般采取的做法是：随机选择轴点元素

五、希尔排序（Shell Sort）

• 希尔排序把序列看作是一个矩阵，分成m列，逐渐进行排序，当m从某个整数逐渐减为1，整个序列将完全有序，因此，希尔排序也被称为递减增量排序
• 矩阵的列数取决于步长序列，比如，如果步长序列为{1,5,19,41,109...}，就代表依次分成109列、41列、19列、5列、1列进行排序，不同的步长序列，执行效率也不同
• 希尔本人给出的步长序列是 n/(2^k)，比如n为16时，步长序列时{1,2,4,8}
• 希尔排序的本质是逐渐减少逆序对
• 希尔排序底层一般使用插入排序对每一列进行排序，因此也有很多资料认为希尔排序是插入排序的改进版

void insertSort(int *arr,int len,int step)
{
    for (int col = 0; col<step; col++) {
        for (int i = col + step; i < len; i += step) {
            int index  = i;
            int value = arr[i];
            while (index > col && value < arr[index - step]) {
                arr[index] = arr[index - step];
                index -= step;
            }
            arr[index] = value;
        }
    }
}

void ShellSort(int *arr,int len)
{
    for (int i = len >> 1; i>0; i = i >> 1) {
        insertSort(arr, len, i);
    }
}

希尔排序性质分析

• 稳定性：不稳定排序
• 空间复杂度：O(1)
• 时间复杂度：
  • 最好情况是步长序列只有1，且序列几乎有序，时间复杂度为O(n)
  • 希尔本人给出的步长序列，最坏情况时间复杂度是O(n^2)
  • 目前已知的最好的步长序列，最坏时间复杂度是O(n^(4/3))