排序算法

算法思想，时间复杂度–平均、最好、最差，空间复杂度，排序方式，稳定性。

时间复杂度：

关于时间复杂度：

平方阶O(n^2)排序：各类简单排序—冒泡排序，直接插入排序和选择排序
线性对数阶(O(nlogn)): 快排，堆排序和归并排序。
线性阶O(n) 基数排序，桶排序。

空间复杂度：

稳定性定义：排序前后两个相等的数相对位置不变，则算法稳定重点在于：两个相等数，排序前后相对位置不变(a=b,排序前a在前，b在后；排序后，a,b顺序不变)。

稳定性得好处：从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。

稳定排序：冒泡排序，插入排序，归并排序和基数排序不稳定：选择，快排，希尔和堆排序。

冒泡排序

算法思想

比较相邻两个元素，如果前一个元素比后一个元素大，则交换两个元素；否则，继续比较，直到到达最后一个元素，那么，最后一个元素是最大的；
再次从头比较，n个元素，一共进行n-1趟从头比较，同时每趟比较的元素对逐渐减少。

代码实现

void bubbleSort(vector<int>& array){
    //记录比较趟树
    for (int i=1; i<array.size(); i++){
        //当前轮次是否发生交换
        bool flag = false;//默认没有交换
        for (int j=0; j<array.size()-i; j++){
            if (array[j] > array[j+1]){
                swap(array[j], array[j+1]);
                flag = true;
            }
        }
        //没有发生交换，说明有序，退出,减少比较趟数
        if (flag == false)
            break;
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(N^2)	O(N)	O(N^2)

最好时间复杂度：数组已经有序，进行一趟比较，在这一趟比较过程中，没有发生交换。最差时间复杂度：数组逆序，进行n-1趟比较，

空间复杂度

O(1). 仅仅声明了3个变量(or 4个加一个temp变量)。

稳定性

稳定。

相等元素之间的先后关系，排序先后过程中，并不会改变—只有前面元素大于后面元素才发生交换。

Sorting In Place

Yes。就地排序(直接对原数组进行修改)。

选择排序

算法思想

从头到尾逐个比较，找到最小/最大元素，然后将它放到合适的位置(最前/最后)。
一共进行n-1趟查找。

代码实现

void selectionSort(vector<int>& array){
    //n-1趟查找
    for (int i=0; i< array.size()-1; i++){
        // minIndex用来减少交换次数
        int minIndex = i;//当前值设为最小值
        // 在下标为[i+1, n)范围内查找最小值
        for (int j=i+1; j<array.size(); j++){
            if (array[j] < array[minIndex])
                minIndex = j;
        }
        // 减少交换次数： 如果当前值为最小值，不进行交换
        if (minIndex != i)
            swap(array[i], array[minIndex]);
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(N^2)	O(N^2)	O(N^2)

无论数组有序、逆序或者乱序，算法比较次数永远不变。

空间复杂度

O(1). 声明了2个临时变量(记录最小index，以及用于交换的temp)。

稳定性

不稳定。

(7) 2 5 9 3 4 [7] 1，第一趟查找后，变成 1 2 5 9 3 4 [7] (7) 两个相等元素，在排序过程中，先后顺序发生了改变。

Sorting In Place

Yes。就地排序–直接修改数组。

插入排序

算法思想

将数组的第一个元素视为有序子序列，然后将后面的n-1个元素逐个插入到有序子序列的合适位置，直到有序子序列长度等于n。
进行n-1趟插入；每次插入过程需要在有序子序列中找到合适的位置(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面)。

代码实现

void insertionSort(vector<int>& array){
    for(int i=1; i<array.size(); i++){
        // 待插入元素
        int temp = array[i];
        int j = i;//新有序子序列的后界
        //寻找合适的位置：移动
        // 当有序子序列中元素比待插入值大时，往后移动
        while (j>0 && temp < array[j-1]){
            array[j] = array[j-1];
            j--;
        }
        //找到合适位置:j前一个元素比temp小(或者相等)，所以j就是合适的位置
        array[j] = temp;
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(N^2)	O(N)	O(N^2)

最好时间复杂度：数组已经有序，进行n-1次大循环，每次大循环中，当前元素正好比有序子序列的最大值还大(本身所在的位置就是合适的位置)。最差时间复杂度：数组逆序，进行n-1大循环，每次大循环进行i-1次移动。

空间复杂度

O(1).

稳定性

稳定。当前值和有序子序列相等时，不发生移动，放在相等元素之后。

Sorting In Place

Yes.

希尔排序

希尔排序，也叫递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序树基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数组操作时，效率高，即可达到线性排序的效率
但插入排序一般来说是低消的，因为插入排序每次只能将数据移动一位

算法思想

选择一个增量序列t1,t2,.ti..tj…,tk,其中ti > tj,tk=1
按增量序列个数k，对序列进行k趟排序
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各个子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列长度。

代码实现

void shellSort(vector<int>& array){
    // 对gap进行赋值：确定gap的增量子序列
    int gap = 1;
    while (gap < array.size())
        gap = gap * 3 + 1;

    // 开始排序
    while (gap > 0){//确定循环条件，最终gap等于1，进行全表的插入排序
        //从gap开始，对每个子序列进行插入排序
        // array[i]会根据i-gap确定所属的子序列的后界
        // 比如说0,1,2,3,4；gap=4 len=5;arr[4]属于第一个子序列，arr[5]第二个子序列
        // 自动寻找：通过i-gap
        for (int i=gap; i<array.size(); i++){
            int temp = array[i];//当前插入值
            int j = i;//子序列新的后界
            //在子序列中找到合适的位置
            while (j >= gap && array[j-gap] > temp){
                array[j] = array[j-gap];
                j -= gap;
            }
            array[j] = temp;
        }
        // 增量更新，越来越小，直至等于1--进行直接插入排序。因为此时已经几乎有序，速率很快，接近线性
        gap /= 3;
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(NlogN)	O(Nlog^2N)	O(Nlog^2N)

空间复杂度

O(1).

稳定性

不稳定。

直接插入排序是稳定的，因为增量为1，而希尔排序并不稳定，因为当增量大于1时，两个相等元素的先后顺序可能因为处于不同的子序列而发生改变。

Sorting In Place

Yes。

归并排序

算法思想

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入合并空间，并移动指针到下一个位置
重复直到某一指针到达序列尾
将另一序列添加到合并空间

分分分，只剩下一个元素—有序，然后两个序列进行合并，知道合并全部元素为止。

代码实现

void merge(vector<int>& array, int left, int mid, int right){
    int i,j,k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> leftPart;
    vector<int> rightPart;
    for (i=0; i<n1; i++)
        leftPart.push_back(array[left + i]);
    for (j=0; j<n2; j++)
        rightPart.push_back(array[mid+1+j]);
    i = 0, j=0, k=left;
    while (i<n1 && j< n2){
        if (leftPart[i] <= rightPart[j])
            array[k++] = leftPart[i++];
        else
            array[k++] = rightPart[j++];
    }
    while (i < n1)
        array[k++] = leftPart[i++];
    while (j < n2)
        array[k++] = rightPart[j++];
}
void mergeSort(vector<int>& array, int left, int right){
    if (left < right){
        // 不用(left+right)/2,理由：防止溢出
        int mid = left + (right - left)/2;
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(NlogN)	O(NlogN)	O(NlogN)

最好时间复杂度：数组已经有序，进行一趟比较，在这一趟比较过程中，没有发生交换。最差时间复杂度：数组逆序，进行n-1趟比较，

空间复杂度

O(N). 需要声明新的空间，存储排序后的结果；或者，声明长度和等于数组长度的空间，然后将左右两部分分别加入到两个对应的数组中，然后进行“merge”运算。

稳定性

稳定。

Sorting In Place

Out-place。不是就地排序(声明新空间)。

快速排序

算法思想

从数列中跳出一个元素，称为“基准”(pivot)
重新排序数列，所有元素比基准值小的摆放在基准元素前面，所有比基准元素大的放在基准元素后面(相同的元素可以放在任意一边)。在这个分区退出之后，该基准就处在数列的合适位置，这个过程称为“partition”操作
递归地把小于基准值元素的子序列和大于基准值元素的子序列排序

代码实现

partition函数特点：将小于pivot的元素放在左边，大于pivot的元素放在右边。可以用来寻找倒数第k个元素，或者第k小的元素。

int partition(vector<int>& array, int left, int right){
    // 基准值pivot
    int pivot = array[right];
    // 小于pivot的有序序列的下标
    int i = left - 1;
    // 遍历，将元素放到合适位置
    for (int j=left; j<= right-1; j++){
        if (array[j] <= pivot){
            i++;
            swap(array[i], array[j]);
        }
    }
    // 将pivot摆放到合适的位置
    swap(array[i+1], array[right]);
    // 返回基准元素的位置
    return i+1;
}
void quickSort(vector<int>& array, int left, int right){
    if (left < right){
        int pi = partition(array, left, right);
        quickSort(array, left, pi-1);
        quickSort(array, pi+1, right);
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(NlogN)	O(NlogN)	O(N^2)

最好时间复杂度：数组已经有序，平衡二叉树最差时间复杂度：数组逆序，pivot每次都是当前待排序的最值，构成一颗偏树。

空间复杂度

O(logN). 递归实现调用堆栈大小。

稳定性

不稳定。

Sorting In Place

Yes。

堆排序

堆结果局部有序, 存储结构用数组存储，表示可以用二叉树表示，堆其实是一个完全二叉树。

如果数组以0下标开始，那么编号为i的节点，左孩子编号为2i+1, 右孩子为2i+2；双亲节点编号为floor((i-1)/2); 如果数组以1下标开始，那么编号为i的节点，左孩子编号为2i，右孩子编号为2i+1；双亲节点编号为floor(i/2);

我们先将数组构建成大顶堆[建堆]，然后逐渐将大顶堆变成有序数组(假删除)[去堆]。

算法思想

创建一个堆H0,….,n-1
把堆首(最大值/最小值)和堆尾互换
把堆的尺寸缩小1，(删除堆尾元素，放在数组合适的位置),调整堆首元素位置，形成新的堆
重复，直到堆只剩一个元素

代码实现

当前数组可以看做是一个堆，但是并不满足大顶堆的性质，所以需要调整；这个过程中并不会有插入数据，或者说是新建数据的发生。

// n 堆大小； i调整的当前节点编号
void heapify(int arr[], int n, int i){
    // 找到最大值的下标
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    //确保对应节点存在
    if (left < n && arr[left] > largest)
        largest = left;
    if (right < n && arr[right] > largest)
        largest = right;
    // 开始调整：交换
    if (largest != i){//说明不符合堆性质，需要调整
        swap(arr[i], arr[largest]);
        // 继续调整
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n){
    // 把arr当做一个堆，但是需要调整使它符合大顶堆性质
    // 从最后一颗子树开始
    for (int i = n/2-1; i>=0; i--)
        heapify(arr, n, i);
    // 开始排序：缩小堆尺寸，反复调整堆，符合大顶堆性质
    for (int i=n-1; i>=0; i--){
        // 假删除堆顶元素，放到末尾，最终排序的位置
        swap(arr[0], arr[i]);
        // 调整堆首节点---堆大小改变
        heapify(arr, i, 0);
    }
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(NlogN)	O(NlogN)	O(NlogN)

空间复杂度

O(1). 数组本身看做是一个堆，堆的大小不发生变化(假变化)。

稳定性

不稳定。

Sorting In Place

Yes。

计数排序

算法思想

根据数组中元素取值范围，新建一个数组，统计各个元素出现的次数。然后根据统计结果，依次输出就是排序结果；新建空间，将输出结果保存，然后再将保存结果赋值给原数组实现排序。

代码实现

void countSort(vector<int>& arr){
    // 确定数据取值范围
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    int range = max - min + 1;
    // 根据取值范围，新建存储空间：存统计量 & 临时排序结果
    vector<int> count(range), output(arr.size());
    // 开始统计：base-zero
    for (int i=0; i<arr.size(); i++)
        count[arr[i]-min]++;
    // 调整count结果:
    // count值更新为在有序数组的终止下标(based-one)
    for (int i=1; i<range; i++)
        count[i] += count[i-1];
    // 将排序结果临时保存:从后往前
    for (int i=arr.size()-1; i>=0; i--){
        // 将arr[i]放到合适的位置
        // arr[i]-min是在count数组中的下标 
        // count[arr[i]-min],base-one的终止下标，所以要减一
        output[count[arr[i]-min]-1] = arr[i];
        // 更新终止下标位置
        count[arr[i]-min]--;
    }
    // 将临时结果保存给arr
    for (int i=0; i< arr.size(); i++)
        arr[i] = output[i];
}

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(N+K)	O(N+K)	O(N+K)

K是数据取值范围大小。统计N个元素数组，将统计结果放到K个元素的映射表中，然后根据映射表摆放排序结果。不是基于选择和交换的排序。

空间复杂度

O(K)。K是数据取值范围大小。

稳定性

稳定。

Sorting In Place

Out Place.

桶排序

算法思想

算法思想和计数排序差不多，只不过计数排序中count数组里每个位置代表一个取值，而桶排序中每个桶代表一个取值范围，桶的取值区间依次变大。所以桶排序的关键在于，如何将数组中的数据映射到代表不同范围的桶里。

要解决的问题有：

要声明多少个桶？
如何将数据映射到代表不同取值范围的桶中？
如何将不为空的桶拼接成最终排序结果？

问题一：

代码实现

1
2

时间复杂度

平均时间复杂度	最好时间复杂度	最差时间复杂度
O(N+K)	O(N+K)	O(N*N)

空间复杂度

O(N+K)

稳定性

稳定。

Sorting In Place

out place。

基数排序

应用场景：正整数。

算法思想

将所有待比较数值(正整数)统一为同样的数位长度，数位较短的数前面补零
从最低位开始，依次进行一次排序
排序结束后，数列就变成了一个有序数列

代码实现

// 统计数组中的最大值
int getMax(int arr[], int n){
    int result = arr[0];
    for (int i=1; i<n; i++)
        if(arr[i] > result)
            result = arr[i];

    return result;
}
// 基数排序中的计数排序：exp表示当前的基数
// 由它来计算当前位的数字；exp变化从1到10到100...
void countSort(int array[], int n, int exp){
    // 临时保存数组
    int output[n];
    int i,count[10] = {0};//默认为10进制
    // 统计
    for (i=0; i<n; i++)
        count[(array[i]/exp)%10]++;
    // 更新count
    for (i=1; i<10; i++)
        count[i] += count[i-1];

    // 临时保存排序结果
    for (i=n-1; i>=0; i--){
        output[count[(array[i]/exp)%10]-1] = array[i];
        count[(array[i]/exp)%10]--;
    }
    // 保存到arr中
    for (i=0; i<n; i++)
        array[i] = output[i];
}
// 10进制
void radixSort(int arr[], int n){
    int m = getMax(arr, n);
    for (int exp=1; m/exp >0; exp *= 10)
        countSort(arr, n, exp);
}