leetcode刷题c++各类排序总结

写在前面：

对于数据结构和算法来说，排序是最基础的，也是初学时理解较为困难的，这里作以记录，便于我自己复习，也是更加深我自己的理解

1、冒泡排序

冒泡排序几乎是最先了解的排序算法，思想也很简单：
如果每次我们将相邻元素进行对比，并且把较大的元素交换（swap）到后面，那么通过一轮的相邻对比，数组最后的元素就是这个数组中最大的元素。
那么我们进行n轮对比，每次对前n个元素进行相邻比较和交换，那么最终就会得到一个有序的数组。
实现如下 ：

void bubble(int *arr,int n) {//冒泡排序
    //每一趟比较后把这一趟找到的最大元素放到数组最后
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {//注意j<n-1，小心溢出
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

这里我们经常会用到swap的动作，初学时一般使用这样的方法进行交换：
假如有两个int类型的变量a和b

    int temp = a;
    a = b;
    b = temp;

所以，可以定义一个swap函数，方便后续的交换：

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

这里需要使用引用的方式将参数传入函数

int i;
int &j = i;
相当于说“j是i的一个别名”
声明引用的同时必须初始化‘&j = i’ 指向一个已经存在的对象
一旦一个引用被初始化，不能指向其他对象

复杂度：
对冒泡排序来说，平均时间复杂度：O(n2)

2、选择排序

选择算法的思想是：
每次找到这一趟中的最小数，放在数组的开头（位置是走的趟数）
第一趟找到所有n个元素中最小的，放在第一个元素
第二趟找到后n-1个元素中最小的，放在第二个元素
……
第n-1趟找到后两个元素中最小的，放在第n-1元素（倒数第二个）
第n趟找到最后一个元素中最小的，放在第n个元素（最后一个）
实现：

void select(int* arr, int n) {//选择排序
    //每一次找到当前的最小数，放在这次的位置，第一次放在第一个，第二次放在第二个……
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            swap(arr[i], arr[min]);
        }
    }
}

复杂度：
对选择排序来说，平均时间复杂度：O(n2)

3、插入排序

插入排序的思想，类似扑克牌整理：
假设前m个元素已经有序，对第m+1个元素，向前比较，直到找到新插入的元素（扑克牌）的位置
继续对第m+2个元素插入
直到第n个元素完成插入，数组有序

void insert(int* arr, int n) {//插入排序（扑克牌洗牌
    //在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
    for (int i = 1; i < n; i++) {
        while (i-1>=0&&arr[i]<arr[i-1])
        {
            swap(arr[i], arr[i - 1]);
            i--;
        }
    }

}

说明：这里i-1>=0，即为i>=1，也就是说，插入排序每次比较的时候，都是以1为gap进行比较的，这里的理解对完成 希尔排序 有很大帮助

复杂度：
对插入排序来说，平均时间复杂度：O(n2)

4、希尔排序

思想：
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

实现：

void shell(int *arr,int n) {//如果数据序列基本有序，使用插入排序会更加高效。
    for(int gap=n/2;gap>0;gap=gap/2){
        for (int i = gap; i < n; i++) {
            while (i-gap >=0 && arr[i] < arr[i - gap]) {
                swap(arr[i], arr[i - gap]);
                i = i - gap;
            }
        }
    }
}

说明：
对希尔排序的理解，可以理解为，每次插入排序的时候，gap不为1。这就意味着，其实希尔排序是分组按照gap规定的组进行插入排序的
每次 gap /= 2(gap=gap/2)，最终就是当gap为1时，其实就是在插入排序，所以说希尔排序是在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。

复杂度：
对希尔排序来说，平均时间复杂度：希尔排序时间复杂度是 O(n^(1.3-2))

5、归并排序

思想：
merge函数用于将两个有序的数组合并为一个数组
实现：只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

void merge(int a[], int temp[], int l, int r, int mid) {
    int i = l;//左半区第一次没排序元素
    int j = mid+1;//右半区第一次没排序元素
    int t = l;//temp临时数组下标

    while (i <= mid && i <= r) {
        if (a[i] <= a[j]) {
            temp[t] = a[i];
            t++;
            i++;
        }
        else {
            temp[t] = a[j];
            t++;
            j++;
        }
    }
    while (i <= mid) {
        temp[t] = a[i];
        t++;
        i++;
    }
    while (j <= r) {
        temp[t] = a[j];
        t++;
        j++;
    }

    while (l<=r) {
        a[l] = temp[l];
        l++;
    }
}

归并排序入口：

void msort(int *arr,int *temp,int l,int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        //左半区递归
        msort(arr, temp, l, mid);
        //右半区递归
        msort(arr, temp, mid + 1, r);
        //合并函数
        merge(arr,temp,l,r,mid);
    }
}
void Merge(int* arr, int n) {
    int* temp = new int[n];
    for (int i = 0; i < n; i++) {
        temp[i] = 0;
    }
    //show(temp, n);
    msort(arr, temp, 0, n - 1);
    //show(temp,n);
    
};

复杂度：
对归并排序来说，平均时间复杂度：平均时间复杂度：O(NlogN)
计算：设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。

6、堆排序

思想：
利用堆的性质：

大顶堆，子孩子都小于父节点
对下标为i的节点，父节点为(i-1)/2，左孩子节点i2+1，右孩子节点i2+2
一般用数组存储顶堆
小顶堆，父节点小于等于孩子节点
数组存储，大顶堆顺序大到小，小顶堆顺序小到大

因为大顶堆的堆顶是最大的数，每次把它取出，维护大顶堆，让堆顶再次成为最大的数，反复这个过程，就能实现排序。
实现：
大顶堆维护：

void heapify(int arr[], int len, int i)
{
    int largest = i;
    int lson = i * 2 + 1;
    int rson = i * 2 + 2;

    if (lson < len && arr[largest] < arr[lson])
        largest = lson;
    if (rson < len && arr[largest] < arr[rson])
        largest = rson;
    if (largest != i)
    {
        swap(arr[largest], arr[i]);
        heapify(arr, len, largest);
    }
}

堆排序入口：

// 堆排序入口
void heap_sort(int arr[], int len)
{
    int i;
    // 建堆
    for (i = len / 2 - 1; i >= 0; i--)//i=(len-2)/2//其实是假设最后一个数为右子结点求出的父节点下标
    {
        heapify(arr, len, i);
    }

    // 排序
    //建堆完成之后，相当于最大值在堆顶，每次把最大值取出，然后重新排序剩下的堆
    for (i = len - 1; i > 0; i--)
    {
        swap(arr[i], arr[0]);
        heapify(arr, i, 0);//这里的i就是len-1，其实就是新的len（新的数组长度
    }
}

平均时间复杂度：O(NlogN)
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。

7、快速排序

思想：
基本思想：（分治）

先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。

可以这样理解：
挖坑填数

数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85

初始时 i = 0; j = 9; key=72
由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。
这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。
这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。
数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85

此时 i = 3; j = 7; key=72 再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。 此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将key填入a[5]。
数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85

实现：

void q_sort(int *arr, int l, int r) {//left和right两个指针
        //先从数列中取出一个数作为key值；
        //将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
        //对左右两个小数列重复第二步，直至各区间只有1个数。
    if (l > r)
        return;
    int i = l;
    int j = r;
    int val = arr[l];
    while(i<j) {
        while (arr[j] >= val&&i<j) {//从右向左找到一个小于val的值
            j--;
        }
        if (i < j) {
            arr[i]=arr[j];//小于val的值与val交换
            i++;
        }
        while (arr[i] <= val && i < j) {//从左向右找到一个大于新的val的值
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];//大于val的值与新val值交换
        }
    }
    arr[i] = val;//最终找到i使前面的都小于val，后面的都大于val
    //递归对左右部分递归
    q_sort(arr,l,i-1);
    q_sort(arr,i+1,r);
}

函数入口：

void quick(int *arr,int n) {

    q_sort(arr,0,n-1);
}

复杂度：
平均时间复杂度：O(N*logN)

排序算法选择总结：常用快速排序，需要考虑空间复杂度时使用堆排序，需要考虑稳定性时使用归并排序。

以上，就是我个人的一些记录，在我看来，真理无穷，无限进步吧！

我是栗子，祝你幸福。