排序算法

冒泡排序

冒泡排序的基本思想是，每一次冒泡，都从数组末端将最小的数或者最大的数冒泡到最上端。
时间复杂度为o(n^2)。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        if(nums.size() <=1) return nums;
        
        for(int i = 0; i<nums.size(); i++){
            for(int j = nums.size()-1; j>i; j--){
                if(nums[j] < nums[j-1]){
                    swap(nums, j, j-1);
                }
            }
        }
        
        return nums;
        
    }
    
    void swap(vector<int>& nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
};

选择排序

选择排序思想有点类似于冒泡排序，都是在一次排序后把最小的元素放到最前边。但是过程不同。
冒泡排序是通过交换相邻元素。而选择排序是通过对整体的选择。
例如，对[5,3,8,6,4]进行选择排序：

1. 5和剩余序列[3, 8, 6, 4]中最小的元素交换。变为[3, 5, 8, 6, 4]。
2. 5和剩余序列[8, 6, 4]中最小元素交换。变为[3, 4, 8, 6, 5]。
3. 依次类推
   可以看出时间复杂度仍为O(n^2)。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        if(nums.size() <=1) return nums;
        
        for(int i = 0; i<nums.size(); i++){
            int minIdx = i;
            for(int j = i+1; j<nums.size(); j++){
                if(nums[j] < nums[minIdx]){
                    minIdx = j;
                }
            }
            
            if(minIdx != i){ //如果发现了剩余序列的最小值
                swap(nums, i, minIdx);
            }
        }
        
        return nums;
    }
    
    void swap(vector<int>& nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
};

插入排序

例如[5, 3, 8, 6, 4]进行排序。

1. 假设第一个数5位置是对的
2. 下一个拿到3，就要把3放在5前边，5向后移位
3. 以此类推，要保证每一次插入，前边的序列是有序的。
   时间复杂度仍然为O(n^2)。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        if(nums.size() <=1) return nums;
        
        for(int i = 1; i<nums.size(); i++){
            int j = i;
            int target = nums[i];
            while(j > 0 && target < nums[j-1]){
                nums[j] = nums[j-1]; //向后移位，这时原本的nums[i]已经保存成了target
                j--;
            }
            nums[j] = target;
        }
        
        return nums;
        
    }
    
};

快速排序

快速排序是冒泡+二分法。在冒泡排序中，每一次只能把整个序列的一个最值浮出来。而快速排序实现了一次遍历将最小和最大分别移到中点两侧。思路是：两个指针，右指针找比基准大的，左指针找比基准小的。直到相遇。
举例：[5, 3, 8, 6, 4]

1. 以5为中点，将剩余序列分为比5大的和比5小的。左指针指向最左，右指针指向最右。相向遍历。
2. 首先移动右指针还是左指针？。这取决于最后你的左右指针在何处相遇，因为我们要交换基准点和指针相遇处的值。一般我们选择序列第一个值为基准点，那么我们需要指针相遇在小于基准点的那个界限，这样才符合我们的思路。那么我们就需要先移动右指针。如果先移动左指针就会相遇在大于基准点的界限。
3. 在指针相遇之前，如果左指针大于基准，右指针小于基准，那么交换两指针的值，继续进行遍历。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        if(nums.size() <=1) return nums;
        
        quickSort(nums, 0, nums.size()-1);
        
        return nums;
        
    }
    
    void quickSort(vector<int>& nums, int start, int end){
        if(start >= end) return;
        
        int baseP = partition(nums, start, end); //一次遍历，找到基准位置
        quickSort(nums, start, baseP-1);
        quickSort(nums, baseP+1, end);
        
    }
    
    int partition(vector<int>& nums, int start, int end){
        int basePoint = nums[start];
        int leftP = start;
        int rightP = end;
        while(leftP < rightP){
            while(leftP < rightP && nums[rightP] >= basePoint){
                rightP--;
            }
            while(leftP < rightP && nums[leftP] <= basePoint){
                leftP++;
            }
            
            swap(nums, leftP, rightP);
        }
        swap(nums, start, leftP);//将基准换到中间去
        return leftP; //返回当前基准点的位置
    }
    
    void swap(vector<int>& nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
};

堆排序

1. 什么是堆：

堆（Heap）是一种具有如下性质的二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
也就是：
大顶堆满足 root > left && root > right
小顶堆满足 root < left && root < right
这样一种数据结构能够满足，整个堆的根节点一定是最大值或者最小值。

2. 堆排序：

根据堆这种数据结构进行选择排序，也就是一个一个确定最大数或最小数（遍历n），然后再对剩余序列进行操作（遍历logn），最坏最好时间复杂度均为O(nlogn)。也是不稳定排序。

3. 用线性数组表示堆：

• 现在我们用先序遍历二叉树得到一个线性数组，那么此时root和child之间的下标关系是什么呢。
• 我们知道每一个root至多对应两个child，在堆中不允许出现空缺叶节点。所以：
• 第i行总共有$2^{i-1}$个节点
• 等比数列可知，第i行最后一个节点下标为$2^i-1-1 = 2^i-2$
• 第i行的第一个节点下标为$2^{i-1}-2+1 = 2^{i-1}-1$
• 所以第i行的第m个节点下标为$root=2^{i-1}+m-2$
• 那么第i行的第m个节点对应的左节点为第i+1行的第$(m-1)*2+1$个节点，也就是下标为$left=2^{i}-2+2*(m-1)+1=2^{i}+2*m-3=2*(2^{i-1}+m-2)+1=2*root+1$
• 同理$right=2*root+2$

  4. 堆排序算法：

  堆排序算法要解决两个问题：
• 如何从无序数组构建一个堆
  考虑一个root根节点，如何实现一个堆。（以大顶堆为例）
  第一，找到两个子节点中最大的那个large
  第二，如果root>large那么该根节点已经满足
  第三，如果root<large，那个交换root和large，此时注意，该节点的结构发生了变化，要跟踪root表示的值以及其子树的变化
  第四，从第一个非叶子节点开始遍历，一直到堆顶。第一个非叶子节点一般取（n/2）
• 在输出堆首后，如何重建堆
  重要的是升序大顶堆，降序小顶堆因为在最后构建排序数组的时候要堆顶出栈，而堆顶出栈肯定不能仍然放在堆顶，那么只能放在最末端。
  算法实现：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        if(nums.size() == 0 || nums.size() == 1){
            return nums;
        }
        
        for(int i = nums.size()/2; i>=0; i--){
            //构建大推顶
            heapAdjust(nums, i, nums.size()-1);
        }
        
        for(int i = nums.size()-1; i>=0; i--){
            swap(nums, 0, i); //大推顶交换，heap 头一定是最大的，那么放到最末尾去
            heapAdjust(nums, 0, i-1); //重新构建大推顶 
        }
        
        return nums;
    }
    
    
    void heapAdjust(vector<int>& nums, int start, int end){
        //just deal with the start node
        
        //heap head
        int tmp = nums[start];
        
        for(int i = 2*start+1; i<=end; i=i*2+1){ 
            //找到子节点
            //left is 2*start+1, right is 2*start+2
            if(i<end && nums[i]<nums[i+1]){
                i++;//升序用大推顶，找到子节点中较大的那个
            }
            
            //here nums[i] is the largest child
            if(tmp >= nums[i]){
                break; //已经满足大推顶
            }
            
            //swap the top and the smallest child
            nums[start] = nums[i];
            start = i; //check the new heap
            
        }
        //insert the original root to the right place
        nums[start] = tmp;
        
    }
    
    void swap(vector<int>& nums, int i, int j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
    }
    
};

希尔排序

希尔排序是插入排序的一种高效率实现，也叫缩小增量排序。他的依据是，当序列是有序的时候，插入排序的最佳时间复杂度为O(n)。基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

希尔排序的时间复杂度是复杂的，在大量的实验基础上，可以证明在n属于一定范围的时候，时间复杂度约为
O(n^1.3)。

图解见:https://www.cnblogs.com/chengxiao/p/6104371.html

class Solution {
public:
    //插入排序移动法
    vector<int> sortArray(vector<int>& nums) {
        
        if(nums.size()<=1) return nums;
        
        //逐步缩小gap
        for(int gap = nums.size()/2; gap>0; gap/=2){
            //对每个分组进行插入排序。注意这里i++,其实每次对应的是一个分组的添加
            for(int i = gap; i<nums.size(); i++){
                int j = i;
                int tmp = nums[j];
                while(j-gap>=0 && tmp < nums[j-gap]){
                    nums[j] = nums[j-gap];
                    j -= gap; //原版插入排序是减1，现在是减gap
                }
                nums[j] = tmp;
            }
        }

        return nums;
        
    }
    
    //插入排序交换法，其实就是冒泡的变体
    vector<int> sortArray(vector<int>& nums){
        
        if(nums.size() <= 1) return nums;
        
        for(int gap = nums.size()/2; gap>0; gap/=2){
            for(int i = gap; i<nums.size(); i++){
                int j = i;
                while(j-gap >=0 && nums[j] < nums[j-gap]){
                    swap(nums, j, j-gap);
                    j -= gap;
                }
            }
        }
        
    }
    
    //传统交换
    void swap(vector<int>& nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    //不新开辟内存空间
    void swap(vector<int>& nums, int i, int j){
        nums[i] = nums[i] + nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }
    
};

归并排序

归并排序是另一种不同的排序方法，完全使用了分治思想。思路就是，将一个序列看成两个有序的序列进行合并，然后递归解决问题。时间复杂度为O(nlogn)。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        mSort(nums, 0, nums.size()-1);
        return nums;
        
    }
    
    void mSort(vector<int>& nums, int start, int end){
        
        if(start >= end) return;
        
        int mid = (start+end)/2;
        mSort(nums, start, mid); //一分为2
        mSort(nums, mid+1, end);
        merge(nums, start, mid, end); //两个分数组合并
        
    }
    
    void merge(vector<int>&nums, int start, int mid, int end){
        
        vector<int> tmp(end-start+1);
        int i = start;
        int j = mid+1;
        int k = 0;
        
        //两个数组都没遍历完
        while(i<=mid && j<=end){
            if(nums[i] <= nums[j]){
                tmp[k++] = nums[i++];
            } else{
                tmp[k++] = nums[j++];
            }
        }
        while(i<=mid){
            tmp[k++] = nums[i++];
        }
        while(j<=end){
            tmp[k++] = nums[j++];
        }
        
        for(int k = 0; k<end-start+1; k++){
            nums[start+k] = tmp[k];
        }
        
    }
    
};

计数排序

如果面试的过程中面试官要求写一个时间复杂度为O(n)的排序，那么这是可能的。虽然前边的排序方法时间复杂度的下线是O(nlogn)。但确实是有线性时间复杂度的排序，但对待排序的数要满足一定的范围的整数。而且计数排序需要更多的辅助空间。基本思想： 用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。

因为待排序数组是计数数组的下标，那么就要求待排序数组是非负整数。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size() <= 1) return nums;
        
        int MAX = max(nums);
        
        vector<int> count(MAX+1, 0);
        
        for(int i = 0; i<nums.size(); i++){
            count[nums[i]]++;
        }
        
        int k = 0;
        vector<int> res(nums.size(), 0);
        for(int i = 0; i<=max; i++){
            for(int j = 0; j<count[i]; j++){
                res[k++] = i;
            }
        }
        
        return nums;
        
    }
    
    int max(vector<int>& nums){
        int MAX = INT_MIN;
        for(int ele:nums){
            if(ele > MAX){
                MAX = ele;
            }
        }
        return MAX;
    }
}

桶排序

桶排序是计数排序的一种改进和推广。
基本思想：
假设有一组长度为N的待排关键字序列K[1, 2, …, n]。首先将这个序列划分为M个的子区间（桶）。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中（即桶数组B的下标i），那么该关键字k就作为B[i]中的元素（每个桶B[i]都是一组大小为N/M的序列。）接着对每个桶B[i]中的所有元素进行比较排序（也可以使用快排）。然后依次枚举输出B[0]…B[M]中的全部内容即是一个有序序列。

桶排序的高效性体现在映射函数：他必须做到，如果关键字k1 < k2,那么 f(k1) < f(k2)。

举例：

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中的划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分隔成了基本有序的数据块。然后只需要对桶中少量的数据做先进的比较排序即可。

对N个关键字进行桶排序的时间复杂度分为两个部分：

1. 循环计算每个关键字的桶映射函数，时间复杂度为O(N)
2. 利用先进的比较排序算法对每个桶内的所有数据进行排序，时间复杂度为 $\sum O(N_ilog{N_i})$。其中$N_i$为第i个桶的数据量。

显然第2部分是桶排序性能好坏的决定性因素。所以尽量减少桶内数据的数量是提高效率的唯一办法。（因为基于比较排序的最好平均时间复杂度就是O(nlogn)）。因此需要做到两点：

1. 映射函数f(k)能够将N个数据平均分配到M个桶中，这样每个桶就有[N/M]个数据量。
2. 尽量增大桶的数量。极限情况下，每个桶只能得到一个数据（就是计数排序），这样就完全避开了桶内数据的比较排序操作。当然，数据量巨大的情况下，f[k]函数会使桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题。

所以平均时间复杂度为
O(N) + O(M*(N/M)*log(N/M)) = O(N+NlogN-NlogM)

所以当N=M时，即极限情况下每个桶只有一个数据能够达到最好效率O(N)。

例子参考http://www.codeceo.com/article/10-sort-algorithm-interview.html#0-tsina-1-10490-397232819ff9a47a7b7e80a40613cfe1。

基数排序

基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

什么是稳定的排序

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

总结

冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。

1. 从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
2. 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
3. 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。
4. 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
5. 上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。