本文主要内容转载自http://www.cnblogs.com/eniac12/p/5329396.html#s32 和 http://blog.csdn.net/hguisu/article/details/7776068
目录
1. 冒泡排序
2. 选择排序
3. 插入排序
3.1 二分插入排序
3.2 希尔排序
4. 归并排序
5. 堆排序
6. 快速排序
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
这里我们来探讨一下常用的比较排序算法，非比较排序算法将在下一篇文章中介绍。下表给出了常见比较排序算法的性能：
排序算法稳定性：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i] >= A[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。
其次，说一下排序算法稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的。
1. 冒泡排序(Bubble Sort)
冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：
(1) 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
(2) 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
(3) 针对所有的元素重复以上的步骤，除了最后一个。
(4) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的代码如下：
/********** 冒泡排序：BuubbleSort.cpp **********/// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定#include<iostream>#include<stdio.h>using namespace std;void swap(int a[], int i, int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp;} void BubbleSort(int a[],int len){ int i,j; for(i=0;i<len-1;i++) //一共进行len-1次；每次最大元素就像气泡一样"浮"到数组的最后 { for(j=0;j<len-i-1;j++) { if(a[j]>a[j+1]) //大数后移；如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法 swap(a,j,j+1); } }}int main(){ int a[8]={6,5,3,1,8,7,2,4}; BubbleSort(a,8); cout<<"排序结果："; for(int i=0;i<8;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的实现过程如下
2. 选择排序(Selection Sort)
选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：
(1) 初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；
(2) 然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
(3) 以此类推，直到所有元素均排序完毕。
注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
选择排序的代码如下：
/********** 选择排序：SelectionSort.cpp **********/// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- O(n^2)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 不稳定#include<iostream>using namespace std;void Swap(int a[], int i, int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp;}void SelectionSort(int a[], int len){ int i,j; for(i=0;i<len-1;i++) { int min=i; for(j=i+1;j<len;j++) { if(a[j]<a[min]) { min=j; } } if(min!=i) { Swap(a,min,i); } } }int main(){ int a[8]={6,5,3,1,8,7,2,4}; int i; SelectionSort(a,8); cout<<"排序结果："; for(i=0;i<8;i++) cout<<a[i]<<" "; return 0;}
上述代码对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }进行选择排序的实现过程如右图 
选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。
比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。
3. 插入排序(Insertion Sort)
插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌
对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
具体算法描述如下：
(1) 从第一个元素开始，该元素可以认为已经被排序
(2) 取出下一个元素，在已经排序的元素序列中从后向前扫描
(3) 如果该元素（已排序）大于新元素，将该元素移到下一位置
(4) 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
(5) 将新元素插入到该位置后
(6) 重复步骤2~5
插入排序的代码如下：
/********** 插入排序：InsertSort.cpp **********/// 分类 ------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定#include<iostream>using namespace std;void InsertSort(int a[], int len){ int i,j,get; for(i=1;i<len;i++) { get=a[i]; //右手抓到一张新扑克牌 j=i-1; //左手有序的手牌 while(j>=0 && get<a[j]) //将抓到的新牌与手牌从右往左比较 { a[j+1]=a[j]; //如果新牌比手牌大，手牌后移 j--; //继续往左比较 } a[j+1]=get; //将新抓到的牌放到合适的位置，形成新的有序手牌 }}int main(){ int a[8]={6,5,3,1,8,7,2,4}; InsertSort(a,8); cout<<"排序结果："; for(int i=0;i<8;i++) cout<<a[i]<<" "; cout<<endl; return 0;} 上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行插入排序的实现过程如下
插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
3.1 插入排序的改进：二分插入排序
对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序，代码如下：
/********** 二分插入排序：InsertSortDichotomy.cpp **********/// 分类 -------------- 内部比较排序// 数据结构 ---------- 数组// 最差时间复杂度 ---- O(n^2)// 最优时间复杂度 ---- O(nlogn)// 平均时间复杂度 ---- O(n^2)// 所需辅助空间 ------ O(1)// 稳定性 ------------ 稳定#include<iostream>using namespace std;void InsertSortDichotomy(int a[], int len){ int i,j,get; int left,mid,right; for(i=1;i<len;i++) { get=a[i]; //新抓的扑克牌 left=0; right=i-1; while(left<=right) //采用二分法定位新牌位置 { mid=(left+right)/2; if(a[mid]>get) right=mid-1; else left=mid+1; } for(j=i-1;j>=left;j--) //将欲插入的新牌位置右边的牌整体右移一个单位 a[j+1]=a[j]; a[left]=get; //将抓到的新牌插入到手牌中 }}int main(){ int a[8]={6,5,3,1,8,7,2,4}; InsertSortDichotomy(a,8); cout<<"排序结果："; for(int i=0;i<8;i++) cout<<a[i]<<" "; cout<<endl; return 0;}
当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。
3.2 插入排序的更高效改进：希尔排序(Shell Sort)
希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
希尔排序的代码如下：
/********** 希尔排序：ShellSort.cpp **********/
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
//代码参考：http://blog.csdn.net/morewindows/article/details/6668714
#include<iostream>
using namespace std;
void ShellSort1(int a[], int n) //按照定义的希尔排序
{
int i, j, gap;
for(gap=n/2; gap>0; gap/=2) //初始步长为n/2，每次减半，直至最后为1
{
for(i=0; i<gap; i++) //直接插入排序
{
for(j=i+gap;j<n;j+=gap)
{
if(a[j]<a[j-gap])
{
int temp=a[j];
int k=j-gap;
while(k>=0 && a[k]>temp)
{
a[k+gap]=a[k];
k=k-gap;
}
a[k+gap]=temp;
}
}
}
}
}
void ShellSort2(int a[], int n) //更为精简的希尔排序：每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序
{
int j, gap;
for(gap=n/2;gap>0;gap/=2)
{
for(j=gap;j<n;j++)//从数组第gap个元素开始
{
if(a[j]<a[j-gap])//每个元素与自己组内的数据进行直接插入排序
{
int temp=a[j];
int k=j-gap;
while(k>=0 && a[k]>temp)
{
a[k+gap]=a[k];
k-=gap;
}
a[k+gap]=temp;
}
}
}
}
int main()
{
int a[8]={6,5,3,1,8,7,2,4};
ShellSort2(a,8);
cout<<"排序结果：";
for(int i=0;i<8;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
4. 归并排序(Merge Sort)
归并排序是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。
1. 递归实现: 是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。
合并相邻有序子序列： 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
2. 非递归(迭代)实现: 首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：
(1) 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
(2) 设定两个指针，最初位置分别为两个已经排序序列的起始位置
(3) 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
(4) 重复步骤3直到某一指针到达序列尾
(5) 将另一序列剩下的所有元素直接复制到合并序列尾
归并排序的代码如下：
/********** 归并排序：MergeSort.cpp **********/
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
#include<iostream>
#include<stdio.h>
using namespace std;
void Merge(int A[], int left, int mid, int right) //合并两个已排好序的数组A[left...mid]和A[mid+1...right]
{
int len = right-left+1;
int *temp=new int[len]; //定义数组temp来存放合并后的序列，大小为len
int index=0;
int i=left; //左指针
int j=mid+1; //右指针
while(i<=mid && j<=right)
{
//temp[index++] = A[i] <= A[j] ? A[i++] : A[j++]; //精简高效版本代码：将A[i]和A[j]中较小的赋值给temp[index]，相应的下标加1
if(A[i]<=A[j])
{
temp[index]=A[i];
i++;
index++;
}
else if(A[j]<A[i])
{
temp[index]=A[j];
j++;
index++;
}
}
while(i<=mid) //左边的序列并未全部赋值到temp中，继续赋值
{
// temp[index++] = A[i++];
temp[index]=A[i];
i++;
index++;
}
while(j<=right) //右边的序列并未全部赋值到temp中，继续赋值
{
// temp[index++] = A[j++];
temp[index]=A[j];
j++;
index++;
}
for(int k=0;k<len;k++) //将temp[0-len]赋值到A数组中对应位置
{
// A[left++] = temp[k];
A[left]=temp[k];
left++;
}
}
void MergeSortRecursion(int A[], int left, int right) //递归实现的归并排序(自顶向下)
{
if(left==right) //当待排序的序列长度为1时，递归开始回溯，进行merge操作
return;
int mid=(left+right)/2;
MergeSortRecursion(A,left,mid);
MergeSortRecursion(A,mid+1,right);
Merge(A,left,mid,right);
}
void MergeSortIteration(int A[], int len) //非递归(迭代)实现的归并排序(自底向上)
{
int left, mid, right; //子数组索引,前一个为A[left...mid]，后一个子数组为A[mid+1...right]
for(int i=1;i<len;i=i*2) //子数组的大小i初始为1，每轮翻倍
{
left=0;
while(left+i<len) //后一个子数组存在(需要归并)
{
mid=left+i-1;
right = mid+i < len ? mid+i : len-1; //后一个子数组大小可能不够
Merge(A,left,mid,right);
left=right+1; //前一个子数组索引向后移动
}
}
}
int main()
{
int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大归并排序
int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
int n1 = sizeof(A1) / sizeof(int);
int n2 = sizeof(A2) / sizeof(int);
MergeSortRecursion(A1, 0, n1 - 1); // 递归实现
MergeSortIteration(A2, n2); // 非递归实现
printf("递归实现的归并排序结果：");
for (int i = 0; i < n1; i++)
{
printf("%d ", A1[i]);
}
printf("\n");
printf("非递归实现的归并排序结果：");
for (int i = 0; i < n2; i++)
{
printf("%d ", A2[i]);
}
printf("\n");
return 0;
}上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下
归并排序除了可以对数组进行排序，还可以高效的求出数组小和（即单调和）以及数组中的逆序对，详见这篇博文。
5. 堆排序(Heap Sort)
堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
堆排序：在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列。
堆排序（Heap Sort）只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。
5.1 堆的存储
一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。
（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）
如第0个结点左右子结点下标分别为1和2。
如最大化堆如下：
左图为其存储结构，右图为其逻辑结构。
5.2 堆排序的实现
实现堆排序需要解决两个问题：
1.如何由一个无序序列建成一个堆？
2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
先考虑第二个问题，一般在输出堆顶元素之后，视为将这个元素排除，然后用表中最后一个元素填补它的位置，自上向下进行调整：首先将堆顶元素和它的左右子树的根结点进行比较，把最小的元素交换到堆顶；然后顺着被破坏的路径一路调整下去，直至叶子结点，就得到新的堆。我们称这个自堆顶至叶子的调整过程为“筛选”。
从无序序列建立堆的过程就是一个反复“筛选”的过程。
(1) 构造初始堆
初始化堆的时候是对所有的非叶子结点进行筛选。最后一个非终端元素的下标是[n/2]向下取整，所以筛选只需要从第[n/2]向下取整个元素开始，从后往前进行调整。
比如，给定一个数组，首先根据该数组元素构造一个完全二叉树。
然后从最后一个非叶子结点开始，每次都是从父结点、左孩子、右孩子中进行比较交换，交换可能会引起孩子结点不满足堆的性质，所以每次交换之后需要重新对被交换的孩子结点进行调整。
(2) 进行堆排序
有了初始堆之后就可以进行排序了。堆排序是一种选择排序。建立的初始堆为初始的无序区。
排序开始，首先输出堆顶元素（因为它是最值），将堆顶元素和最后一个元素交换，这样，第n个位置（即最后一个位置）作为有序区，前n-1个位置仍是无序区，对无序区进行调整，得到堆之后，再交换堆顶和最后一个元素，这样有序区长度变为2。
不断进行此操作，将剩下的元素重新调整为堆，然后输出堆顶元素到有序区。每次交换都导致无序区-1，有序区+1。不断重复此过程直到有序区长度增长为n-1，排序完成。
(3) 堆排序实例
首先，建立初始的堆结构如图：
然后，交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区（有序区显示为黄色），然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置……
重复此过程：
最后，有序区扩展完成即排序完成：
由排序过程可见，若想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。
(4) 代码
假设排列的元素为整型，且元素的关键字为其本身。
因为要进行升序排列，所以用大顶堆。
根结点从0开始，所以i结点的左右孩子结点的下标为2i+1和2i+2。
#include<iostream> using namespace std; void HeapAdjust(int A[],int parent,int length) //对无序堆进行调整，使得A[]成为一个大顶堆 { int temp=A[parent]; //temp保存当前父节点 int child=2*parent+1; //假设根节点的序号为0，则i节点的左孩子为2i+1，右孩子为2i+2 while(child<length) { //若右孩子存在，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if(child+1<length && A[child]<A[child+1]) child++; //如果父结点的值已经大于左右孩子结点的值，则直接结束 if(temp>=A[child]) break; //把孩子结点的值赋给父结点 A[parent]=A[child]; //选取孩子结点的左孩子结点,继续向下筛选 parent=child; child=2*child+1; } A[parent]=temp;}void HeapSort(int A[],int n) //堆排序 { //首先建立大顶堆 for(int i=n/2;i>=0;i--) //非叶节点最大序号值为size/2 HeapAdjust(A,i,n-1); //进行堆排序 for(int i=n-1;i>0;i--) { //最后一个元素和第一个元素交换 int temp=A[i]; A[i]=A[0]; A[0]=temp; //将剩下的无序元素继续调增为大顶堆 HeapAdjust(A,0,i); } } int main() { int A[8]={6,5,3,1,8,7,2,4}; HeapSort(A,8); cout<<"排序结果："; for(int i=0;i<8;i++) cout<<A[i]<<" "; cout<<endl; return 0; } 6. 快速排序(Quick Sort)
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：
(1) 快速排序首先找出一个元素作为基准(pivot)
(2)然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值。如此作为基准的元素调整到排序后的正确位置。
(3)递归快速排序，将其他n-1个元素也调整到排序后的正确位置。
(4) 对每个分区递归地进行步骤1~3，递归的结束条件是序列的大小是0或1，最后每个元素都是在排序后的正确位置，排序完成。
举例说明：假设要排序的序列为
(2) 2(i) 4 9 3 6 7 1 5(j) 首先用2当作基准，使用i和j两个指针分别从两边进行扫描。首先比较2和5，5比2大，j左移
(2) 2(i) 4 9 3 6 7 1(j) 5 比较2和1，1小于2，所以把1放在2的位置
(2) 1 4(i) 9 3 6 7 1(j) 5 比较2和4，4大于2，因此将4移动到后面
(2) 1 4(i) 9 3 6 7(j) 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变
经过第一轮的快速排序，元素变为 [1] 2 [4 9 3 6 7 5]。之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。
快速排序的代码如下：
/********** 快速排序：quickSort.cpp **********/
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
// 稳定性 ---------- 不稳定
#include<iostream>
using namespace std;
int QuickSort(int A[],int left,int right)
{
if(left<right)
{
int key=A[left];
int low=left;
int high=right;
while(low<high)
{
while(low<high && A[high]>key)
{
high--;
}
A[low]=A[high];
while(low<high && A[low]<key)
{
low++;
}
A[high]=A[low];
}
A[low]=key;
QuickSort(A,left,low-1);
QuickSort(A,low+1,right);
}
}
int main()
{
int A[8]={6,5,3,1,8,7,2,4};
QuickSort(A,0,7);
cout<<"排序结果：";
for(int i=0;i<8;i++)
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
快速排序是不稳定的排序算法，不稳定发生在基准元素与A[tail+1]交换的时刻。
比如序列：{ 1, 3, 4, 2, 8, 9, 8, 7, 5 }，基准元素是5，一次划分操作后5要和第一个8进行交换，从而改变了两个元素8的相对次序。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/162928.html
