经典排序算法总结与实现

总结排序算法。

交换排序

冒泡排序 BubbleSort

冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

步骤：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。一趟冒泡。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  空间效率：O（1）
  时间效率：最好(表中元素基本有序)是O(n)，平均和最坏都是：O（N2）

int* bubbleSort(int* A, int n) {
      for(int i=n-1;i>0;i--) {
            for(int j=0;j<i;j++) {
                if(A[j]>A[j+1]){
                    swap(A[j],A[j+1]);
                }
            }      
        }
    return A;
}

优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。
优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

快速排序

是所有排序算法中平均时间最好的一种算法，O(nlogn)思想是基于分治法。
思想:在待排序表中任取一个元素作为基准，通过一趟排序将待排序表划分为独立的两部分。使得它左边的元素都小于它，它右边的元素都大于它。这个基准枢纽值放在了最终位置，这是一趟快速排序。
然后分别递归对两个子表重复上述过程。使得每部分只有一个元素或0为止。

时间复杂度：O(n2)
空间复杂度：O(logn)

递归实现：

void swap(int* a,int* b){
        int temp = *a;
        *a = *b;
        *b = temp;
}
int Partition(int* A,int first,int last){
        int pivot = A[first];
        int low = first + 1,high = last;
    	while(low <= high){
            while(low <= high && A[low] <= pivot) low++;
            while(low <= high && A[high] > pivot) high--;
            if(low < high)
                swap(&A[low++],&A[high--]);
        }
        swap(&A[first],&A[high]);
        return high;
}
void QSort(int* A,int first,int last){
        if(first < last){
        	int x = Partition(A,first,last);
        	QSort(A,first,x - 1);
        	QSort(A,x + 1,last);
        }
}
int* quickSort(int* A, int n) {
        QSort(A,0,n - 1);
        return A;
}

应用：

将数组中的大写字母和小写字母分开

最小的K个数

在数组中选中数字的下标是K-1，一趟快速排序后这个数字的左边的数字就是最小的K个数。（不一定有序）

选择排序

简单选择排序

选择排序无疑是最简单直观的排序。它的工作原理如下。

步骤：

• 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 以此类推，直到所有元素均排序完毕。

void selectSort(){
    for (int i=1; i <n; i++) {//进行n-1趟
        min = i;//记录最小元素的位置
        for (int j=i; j<=n; j++){ //从i...n中选择最小元素
            if (A[j]<A[min]) min = j;
            }
    int temp = A[i];//最小元素与A[i]交换
    A[i] = A[min];
    A[min] = A[i];
    }
}

堆排序

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

二叉堆具有以下性质：

• 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
• 每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

步骤：

• 构造最大堆（Build_Max_Heap）：最关键先构造初始堆，反复筛选，自下往上逐步调整为大根堆。
  当建好这个大根堆以后，放到数组中，这是的数组并不是有序化的，接下来就要堆排序。
• 堆排序（HeapSort）：移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
• 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
  时间复杂度：O(nlogn)

建立堆的复杂度是O(n)，只建立一次
调整堆的时间复杂度是o(logn)，调用n-1次 所以是nlogn
不稳定

//i是待调整的数组元素的位置，n是数组的长度
void adjust(int A[],int i,int n){//对A中得前N个元素从第1个元素开始向下调整
        int child,j;
        for(j=A[i];(2*i+1)<n;i=child){
            child=2*i+1;//子结点的位置=2*（父结点位置）+1
            if(child!=n-1&&A[child+1]>A[child]) //得到子结点中较大的结点
                child++;
            if(j<A[child])
                A[i]=A[child];//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
            else break;
        }
        A[i]=j;
    }
void Heapsort(int A[],int n){
        //建立最大堆
       //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
       //n/2-1是最后一个非叶节点，此处"/"为整除
        for(int i=(n-1)/2;i>=0;i--){//从有儿子得最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
            adjust(A,i,n);
        }
        for(int i=n-1;i>0;i--){//将堆顶元素A[0]与当前堆得最后一个元素A[i]换位
            int t=A[0];
            A[0]=A[i];
            A[i]=t;
            adjust(A,0,i);//将有i个节点得新堆从根节点向下调整
        }
    }
int* heapSort(int* A, int n) {
        Heapsort(A,n);
        return A;
        // write code here
}

【补充】
堆的删除：删除堆顶元素的时候，先将堆的最后一个元素与堆顶元素交换，次数堆的性质被破坏，然后进行向下调整操作。再取出最大的元素就是堆顶。反复这个过程。

堆的插入：先将新节点放在堆的末端，再对这个新节点进行向上调整。

堆排序应用

最小的K个数

适用于海量数据。
思想：读入K个数创建一个大小为K的大根堆，依次读入剩余数据，如果当前数据比大根堆小，则用这个数替换当前堆顶，并调整堆使其保证大根堆的性质；如果当前数据比大根堆大，则抛弃。
时间：O(nlogn)

当求最大的K个数时，构建小根堆

插入排序

直接插入

对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤：

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤2~5

排序演示：

空间效率：O（1）
时间效率：O（N2）

int* InsertSort(int* A,int n){
   for(int i=1;i<n;i++){
            int temp=A[i],j=i-1;
            for(;A[j]>temp && j>=0;j--){
                A[j+1]=A[j];
            }
            A[j+1]=temp;
 	}
 	return A;
}

希尔排序

思想：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。插入排序是希尔排序的一种特殊情况，当希尔排序的初始步长为1时，即为插入排序。
时间复杂度：O(n^1.3)

void swap(int* a,int* b){
        int temp = *a;
        *a = *b;
        *b = temp;
    }
int* shellSort(int* A, int n) {
        int gap = n/2;
        while(gap != 0){
            for(int i = gap;i < n;i ++){
                int j = i - gap;
                while(j >= 0){
                    if(A[i] < A[j]){
                        swap(&A[i],&A[j]);
                        i = j;
                        j = j - gap;
                    }
                    else break;
                }
            }
            gap = gap/2;
        }
        return A;
    }

归并排序

有二路归并和多路归并

含义：将两个或俩个以上的有序表合并成为一个新的有序表。
先分解后合并。
时间复杂度：O(nlogn)稳定！

思想：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾.

int* mergeSort(int* A, int n) {
        if(A==NULL || n<=0)    return A;// write code here
        mergesort(A,0,n-1);
        return A;
  }
void mergesort(int* A,int left,int right){
        if(left>=right)  return;
        int mid = left + (right-left)/2;
        mergesort(A,left,mid);
        mergesort(A,mid+1,right);
        Merge(A,left,right,mid);
  }
void Merge(int* A,int left,int right,int mid){
        int* L = new int[mid-left+1];
        int* R = new int[right-mid];
        for(int i=0;i<(mid-left+1);i++){
            L[i] = A[left+i];
        }
        for(int i=0;i<(right-mid);i++){
            R[i] = A[mid+1+i];
        }
        int k=0,m=0;
        int start = left;
        while(k<(mid-left+1) && m<(right-mid)){
            if(L[k] < R[m]){
                A[start++] = L[k];
                k++;
            }else{
                A[start++] = R[m];
                m++;
            }
        }
        while(k<(mid-left+1)){
            A[start++] = L[k++];
        }
        while(m<(right-mid)){
            A[start++] = R[m++];
        }
        delete L;
        delete R;
}

桶排序

时间复杂度为O(n),不是基于比较的排序算法。

计数排序

员工按身高来排序，根据厘米数，依次建立100-300桶，把各自对应的身高放入相对应桶中，所有进入。然后从100号依次倒出，被倒出的顺序就是员工排序的顺序了。

基数排序

十进制的几个数，准备0到9号桶，把每个数根据个位来进入相应的桶，倒出，再根据十位来进入相应的桶，倒出，再根据百位来进入相应的桶，倒出就是最后的顺序了。

已知一个乱序的整数数组，求该数组排序相邻两数的最大间隔，要求时间复杂度为 O(n)。

例如:给定数组为10 23 7 1 35 27 50 41
排序后的结果为:1 7 10 23 27 35 41 50
相邻两数的最大间隔为 13 (10-23)。
遍历数列找到最大最小值(max,min)，则所求的 gap>=(max-min)/n，以(max-min)/n 为步长
建立 k 个桶，每个桶记录落入桶内的最大最小值，顺序比较各个桶之间的最大 gap。

答:用基于桶排序的方式。具体如下:

先找到最小和最大，分别记为 min 和 max，并设置 avg=(max-min)/n
按照 avg 的大小将[min，max]分配(N-1)个桶
将数组中的数存入桶中。
然后按顺序对每个相邻桶(跳过没有数的桶)进行比较，如相邻桶(a, b)(c, d)的距离 D=c-b 最终比较 D 的最大值，则为所求。

总结：

稳定性的概念：
假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，这种排序算法是稳定的，否则不稳定。
（相同值的元素在排序前和排序后，相对次序保持不变。）