排序的特征
- 穩(wěn)定性
穩(wěn)定性是指關(guān)鍵字相同的數(shù)據(jù)哲思，在排序完成后位置會(huì)不會(huì)發(fā)生變化。比如現(xiàn)在一個(gè)成績單粗俱，A的成績是86魁亦，B的成績也是86，現(xiàn)在分別位于 數(shù)組的第10個(gè)位置邀摆，和第11個(gè)位置纵顾。當(dāng)然還有很多其他的人成績，比如一共50個(gè)人栋盹。在對這50個(gè)人排序的完成后片挂，A的位置會(huì)不會(huì)和B的位置交換。如果發(fā)生了交換B出現(xiàn)在了A前面贞盯，不是按照原來的先后順序了音念，發(fā)生這樣的情況就是不穩(wěn)定的排序。如果排序后相同的關(guān)鍵字所在的位置的先后順序并沒有發(fā)生變化就是穩(wěn)定的排序躏敢。 - 內(nèi)排序和外排序
排序過程中待排序的數(shù)據(jù)是否全部被放置在內(nèi)存中闷愤，排序分為內(nèi)排序和外排序。內(nèi)排序所有的數(shù)據(jù)必須全部放在內(nèi)存中件余，外排序是排序記錄的個(gè)數(shù)太多讥脐，內(nèi)存放不下， 需要在內(nèi)外村多次交換數(shù)據(jù)才行啼器。
排序性能影響因素:
- 時(shí)間
主要是比較和移動(dòng)旬渠，高效率的排序算法應(yīng)該是盡量少的移動(dòng)和比較次數(shù) - 空間
空間包括存放數(shù)據(jù)所需要的空間還有其他的輔助空間 - 算法復(fù)雜性
這里是算法本身的復(fù)雜度。
以下的討論中都是對包含n個(gè)整形元素的無序數(shù)組進(jìn)行升序排序端壳。
常見的排序算法
- 冒泡排序
學(xué)習(xí)計(jì)算機(jī)語言時(shí)學(xué)到的最基本的排序算法之一告丢，每兩個(gè)相鄰的元素比較大小，根據(jù)規(guī)則交換位置损谦，第一趟冒泡可以保證第n個(gè)元素歸位岖免，第二趟是n-1位，依次類推照捡。經(jīng)過n趟排序可以使得所有元素歸位颅湘。
下面這個(gè)是一個(gè)非正規(guī)的冒泡排序,它用當(dāng)前位置的元素和后面的元素依次比較，然后交換位置栗精，實(shí)現(xiàn)排序的闯参。
第i次移動(dòng)完成可以保證第i小元素處于正確的位置。
int Arr[] = {9,5,7,6,4,8,1,3,2};
int cnt = sizeof(Arr)/sizeof(Arr[0]);
for (int i = 0; i < cnt ; i++) {
for (int j = i+1; j < cnt; j++) {
if (Arr[i] > Arr[j]) {
int t = Arr[i];
Arr[i] = Arr[j];
Arr[j] = t;
}
}
}
冒泡排序:第i趟排序保證第i大的數(shù)移動(dòng)到相應(yīng)位置，每次都是和相鄰的元素比較的
for (int i = 0; i < cnt ; i++) {
for (int j = 0; j < cnt-i-1; j++) {
if (Arr[j] > Arr[j+1]) {
int t = Arr[j+1];
Arr[j+1] = Arr[j];
Arr[j] = t;
}
}
}
冒泡排序內(nèi)層循環(huán)因?yàn)闆]有條件判斷所以無條件執(zhí)行鹿寨，影響效率新博，比如如果排序的內(nèi)容后半部分本來就是有序的，上述程序依然要走內(nèi)部循環(huán)释移，最差的情況下是數(shù)組本來就是有序的叭披，依然要經(jīng)過兩層循環(huán)判斷寥殖，所以可以考慮增加標(biāo)志位優(yōu)化下玩讳。
int flag = 1;
for (int i = 0; i < cnt && flag == 1; i++) {
flag = 0;
for (int j = 0; j < cnt-i-1; j++) {
if (Arr[j] > Arr[j+1]) { //如果這里一次都沒有走說明從j到n-1的元素本來有序
int t = Arr[j+1];
Arr[j+1] = Arr[j];
Arr[j] = t;
flag = 1;
}
}
}
冒泡算法沒有改進(jìn)前時(shí)間復(fù)雜度固定是O(n^2)改進(jìn)后的，改進(jìn)后 最好的情況下沒有數(shù)據(jù)要交換就是需要進(jìn)行n-1次比較嚼贡，所以時(shí)間復(fù)雜度是O(n)熏纯，最壞的情況下，數(shù)據(jù)都是逆序的粤策，一次交換都不會(huì)少復(fù)雜度是O(n^2）樟澜。
2.選擇排序
for (int i = 0; i<cnt; i++) {
int min = i;//假定當(dāng)前位置的元素的大小是最小的
for (int j = i+1; j < cnt; j++) {//用當(dāng)前位置的元素和后面的元素依次比較，取的最小位置的下標(biāo)
if (Arr[min] > Arr[j]) {
min = j;
}
}
if (min!=i) {//循環(huán)結(jié)束以后交換遍歷得到的最小值和當(dāng)前值的位置
int t =Arr[i];
Arr[i] = Arr[min];
Arr[min] = t;
}
}
選擇排序交換的次數(shù)非常少叮盘。交換次樹等于外部循環(huán)的次數(shù)秩贰。節(jié)約了很多時(shí)間。無論最好還是最壞柔吼。比較的次數(shù)是一樣的第i趟排序需要進(jìn)行n-i次關(guān)鍵字比較毒费，一共需要n*(n-1)/2次。對于交換次數(shù)愈魏，最好時(shí)候是0次觅玻。最差的時(shí)候是n-1次。所以時(shí)間復(fù)雜度為O（n^2),但是因?yàn)榻粨Q的次數(shù)少性能高于冒泡排序
3 . 插入排序
插入排序是通過維持從0到i-1部分是有序的序列培漏，然后通過比較i和i-1的大小溪厘，然后根據(jù)規(guī)則將逆序的元素插入有序序列合適的位置，并且維持0到i-1的元素依然有序牌柄，這樣當(dāng)i =n時(shí)所有的元素都有序了
for (int i = 1; i<cnt; i++) {
//后面的數(shù)據(jù)小于前面的數(shù)據(jù)說明位置反了畸悬。需要插入到有序的序列。[0,i-1]的都是有序的
if (Arr[i]<Arr[i-1]) {
//將Arr[i]插入到[0,i-1]的有序區(qū)間珊佣，并且保證區(qū)間仍然有序
int t = Arr[i];
for (j = i-1; Arr[j] >t ;j--) {
Arr[j+1] =Arr[j];
}
Arr[j+1] = t;
}
}
//這個(gè)是自己寫的傻昙，算不上插入排序，因?yàn)槭遣粩嗟慕粨Q位置保證前面的序列有序的
for (int i = 1; i<cnt; i++) {
//后面的數(shù)據(jù)小于前面的數(shù)據(jù)說明位置反了彩扔。需要插入到有序的序列妆档。[0,i-1]的都是有序的
if (Arr[i]<Arr[i-1]) {
//將Arr[i]插入到[0,i-1]的有序區(qū)間，并且保證區(qū)間仍然有序
for (int j = i; j>0&&Arr[j]<Arr[j-1];j--) {
int t = Arr[j];
Arr[j] = Arr[j-1];
Arr[j-1] = t;
}
}
}
復(fù)雜度分析虫碉。當(dāng)排序本身有序的時(shí)候只是進(jìn)行了比較n-1次贾惦，并沒有一次插入。時(shí)間復(fù)雜度是O(n).最壞的情況下逆序的情況需要比較 1+2+3+..n-1 大約n2/2次，而同時(shí)须板，移動(dòng)次數(shù)也達(dá)到最大值大約是n2/2,如果排序記錄是隨機(jī)的碰镜，概率相同，平均比較和移動(dòng)次數(shù)大約是n^2/4习瑰，所以插入排序比選擇和冒泡要好绪颖。
** 上面三種都是時(shí)間復(fù)雜度為O(n^2)的內(nèi)排序算法。**
4 . 希爾排序
希爾排序是對插入排序的優(yōu)化甜奄。
希爾排序法讓待排序的記錄個(gè)數(shù)減少柠横，將原來的大量記錄數(shù)的記錄分割成多個(gè)組，保證每個(gè)組基本有序课兄‰狗眨基本有序是小的關(guān)鍵字基本在前面，大的基本在后面烟阐，{2搬俊，1，3蜒茄，6唉擂，4，7檀葛，5玩祟，8，9}就可以稱為基本有序驻谆。{1卵凑，5，9胜臊，勺卢，3，8象对，7黑忱，2，4勒魔，6}就不能甫煞。希爾排序采用了分割跳躍的策略，將相聚某個(gè)增量的記錄組成一個(gè)子序列冠绢，在子序列內(nèi)分別進(jìn)行直接插入得到基本有序的結(jié)果抚吠。
int i,j,t;
int increment = cnt;//通過設(shè)置了increment，作為步數(shù)弟胀。達(dá)到先構(gòu)建局部有序的楷力，局部的操作是插入排序
do {
increment = increment/3;
//increment最后的值必須為1喊式，此時(shí)相當(dāng)于插入排序，但是經(jīng)過前面的跳躍
//比較能夠使得數(shù)組基本有序萧朝，所以increment等于1的時(shí)候效率會(huì)很高
//如果最后的increment沒有在等于1的時(shí)候運(yùn)行下面代碼岔留，會(huì)導(dǎo)致某些元素
//漏掉導(dǎo)致排序不成功
for (i = increment+1; i<cnt; i++) {
if (Arr[i]<Arr[i-increment]) {
t = Arr[i];
for (j=i-increment; j>=0&&t<Arr[j]; j-=increment) {//局部的
Arr[j+increment] = Arr[j];
}
Arr[j+increment] =t ;
}
}
} while (increment>1);
因?yàn)椴迦肱判蛟贠(n^2)的算法中，平均效率相對較好检柬，尤其是在元素基本有序的情況下或者記錄較少的時(shí)候會(huì)效率會(huì)提高很多献联，所以希爾排序通過設(shè)置
步長使得數(shù)據(jù)不在相鄰的比較，將數(shù)組按照步長分組何址，使得整體基本有序里逆，然后不斷縮小步長提高效率。increment量的最后必須是1头朱，否則無法完成排序运悲。increment取值為2(t-k+1)龄减，0<=k<=t<=[log2(n+1)]為O(n1.5)项钮。
5 . 歸并排序
歸并排序是利用歸并的思想進(jìn)行排序，假設(shè)排序序列有n個(gè)記錄希停，可以看成n個(gè)有序序列烁巫，每個(gè)子序列的長度為1，然后將每個(gè)子序列的兩兩合并得到n/2向上取整個(gè)有序子序列宠能，然后兩兩合并直到得到一個(gè)長度為n的有序序列亚隙。主要就是分割，合并违崇。
/*
SR中有兩個(gè)有序的子序列分別是[i,m],和[m+1,n]阿弃，將這兩個(gè)子序列合并成一個(gè)有序的序列，放到TR羞延。
*/
void merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,t;
//同時(shí)便利兩個(gè)序列,按大小順序放入TR
for (j=m+1,k=i,t=i;k<=m&&j<=n; t++) {
if (SR[k]<SR[j]) {
TR[t]=SR[k++];
}else{
TR[t]=SR[j++];
}
}
//如果其中一方有剩余渣淳，直接將追加到TR中就可以了
for (; k<=m; k++) {
TR[t]=SR[k];
t++;
}
for (; j<=n; j++) {
TR[t] = SR[j];
t++;
}
}
/*
SR 源數(shù)組，TR1是排序后數(shù)據(jù)存放的數(shù)組伴箩，s表示數(shù)組的起點(diǎn)索引入愧，t表示終點(diǎn)索引
*/
void Msort(int SR[],int TR1[],int s,int t)
{
int m;
int TR2[10];
if (s==t) {//只有一個(gè)元素說明是最小子序列無法繼續(xù)拆分了，直接放入目標(biāo)數(shù)組
TR1[s]=SR[s];
}
else
{
m = (s+t)/2;//講SR平分
//-- 這里的TR2傳值方式是傳遞地址
Msort(SR, TR2, s, m);//對左邊[s,m]歸并為有序的TR2[s,m];
Msort(SR, TR2, m+1, t);//對右邊[m+1,t]歸并到有序的TR2[m+1,t]
merge(TR2, TR1, s, m, t);//將在[s,m]和[m+1,t]分別有序的TR2通過合并算法合并到TR1
}
}
一趟歸并需要將SR[0]到SR[n]相鄰的長度為h的有序序列進(jìn)行兩兩歸并嗤谚，并將結(jié)果放入TR1里面棺蛛，需要將待排序序列所有記錄掃描一遍，耗費(fèi)O(n),整個(gè)歸并排序需要log2n次巩步，所有總的事假復(fù)雜度為nlogn,和原始數(shù)據(jù)的順序無關(guān);歸并排序過程中需要與原始記錄長度相同的控件存放結(jié)果旁赊，以及遞歸時(shí)需要深度為log2n的棧空間椅野，時(shí)間復(fù)雜度是O(n+log2n),并且是一種穩(wěn)定排序的算法终畅，
歸并排序是比較占內(nèi)存钞钙，但是效率缺高穩(wěn)定的算法。
6 . 快速排序
通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分声离，其中一部分記錄的關(guān)鍵字比另一部分小芒炼，可以對這兩部分記錄繼續(xù)進(jìn)行按照這個(gè)規(guī)則排序，使得整個(gè)數(shù)組有序术徊。
void Qsort(int * arr,int start,int end)
{
if (start>end) {
return;
}
int base = arr[start];//取左邊的第一個(gè)元素作為基準(zhǔn)元素
int i = start;
int j = end;
// 基準(zhǔn)數(shù)是任意的本刽，但是為了方便和遞歸方便，所以找可以選擇最左邊的,基準(zhǔn)數(shù)是 //最左邊的時(shí)候要從最右邊開始尋找進(jìn)行j--赠涮。
//這是為了保證一定會(huì)停在比基準(zhǔn)數(shù)大的位置上子寓。
while (i!=j) {
while (arr[j]>=base&&j>i) {//右邊找一個(gè)比基準(zhǔn)數(shù)小的數(shù)，從右邊開始找
j--;
}
while (arr[i]<=base&&i<j) {//左端找比基準(zhǔn)數(shù)大的數(shù)
i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;//找到后交換兩個(gè)數(shù)的位置
}
if (i==j) {//當(dāng)前后相遇的時(shí)候笋除，交換基準(zhǔn)數(shù)和當(dāng)前位置的數(shù)
arr[start] = arr[i];
arr[i] = base;
}
//然后對相遇的左邊序列和右邊序列繼續(xù)遞歸排序
Qsort( arr, start,i-1);
Qsort (arr, i+1 ,end);
}
快速排序的時(shí)間性能斜友，取決于遞歸的深度，在最優(yōu)的情況下垃它，每次都是平分兩半鲜屏，總共需要log2n次，然后每次都是遍歷平分序列需要時(shí)間O(n)国拇，所以最優(yōu)情況O(nlog2n),最壞的情況下洛史，排序的序列為正序或者逆序，每次劃分比上次劃分少一個(gè)記錄的子序列酱吝，另一個(gè)為空也殖，需要進(jìn)行n-1次遞歸調(diào)用，時(shí)間復(fù)雜度為O(n^2)务热，快速排序相當(dāng)于對冒泡排序算法的升級(jí);利用數(shù)學(xué)歸納法可以證明平均情況下時(shí)間復(fù)雜度為nlog2n忆嗜、，算法的效率體現(xiàn)在基準(zhǔn)數(shù)大小崎岂，太大或者太小都會(huì)造成浪費(fèi)捆毫，如果選取的數(shù)總是中間數(shù)的話，while里面的交換次數(shù)就會(huì)增加该镣，相對倆說遍歷過程利用率就高了冻璃，所以快速排序可以在選取基準(zhǔn)數(shù)上進(jìn)行優(yōu)化，這里只是最基本的损合。
7 . 堆排序
堆：堆是完全二叉樹最典型的應(yīng)用省艳。最大堆，完全二叉樹的所有的父節(jié)點(diǎn)都比子節(jié)點(diǎn)大嫁审。反之為最小堆跋炕。這里可以用二叉樹的性質(zhì)來建立堆。用二叉樹的性質(zhì)來描述父子節(jié)點(diǎn)的關(guān)系律适，也可以使用包含左右子樹只針對結(jié)構(gòu)表示節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系辐烂。
堆排序：
將待排序的序列構(gòu)成一個(gè)大頂堆遏插，最大值在堆頂，將最大值與數(shù)組的末尾交換纠修，此時(shí)末尾元素就是最大值胳嘲，然后將剩下的n-1一個(gè)元素重新構(gòu)建成一個(gè)堆，可以得到n個(gè)元素中次大值扣草，反復(fù)執(zhí)行了牛，可以得到一個(gè)有序序列，根據(jù)實(shí)際需求確認(rèn)建立最大堆還是最小堆辰妙。
實(shí)現(xiàn)步驟
- 把無序序列構(gòu)建成完全二叉樹
構(gòu)建完全二叉樹鹰祸。直接用數(shù)組保存樹的節(jié)點(diǎn)，然后利用二叉樹的性質(zhì)實(shí)現(xiàn)樹的遍歷和調(diào)整節(jié)點(diǎn)的位置密浑，比起二叉鏈表的實(shí)現(xiàn)要方便很多蛙婴。
for (int i =1; i<=sum; i++) {
heapArr[i] = arr[i-1];//根據(jù)原始數(shù)組里面的數(shù)據(jù)，構(gòu)建一個(gè)完全二叉樹,完全二叉樹的節(jié)點(diǎn)從1開始尔破，方便計(jì)算
}
- 將完全二叉樹調(diào)整成為堆
可以選擇遞歸方式街图，也可以選擇非遞歸方式。
//在一個(gè)完全二叉樹中調(diào)整curIdx節(jié)點(diǎn)的位置呆瞻，使得完全二叉樹滿足堆的特性
void setNodeP(int curIdx,int maxNode)
{
if (curIdx*2>maxNode) {//這里說明訪問的節(jié)點(diǎn)是葉子節(jié)點(diǎn)
return;
}
int t=curIdx;
//和左子樹比較節(jié)點(diǎn)大小
if (heapArr[curIdx]>heapArr[curIdx*2]) {
//向下調(diào)整
t = curIdx*2;
}
if (curIdx*2+1<=maxNode) {//和右節(jié)點(diǎn)比較大小
if (heapArr[t]>heapArr[curIdx*2+1]) {
t =curIdx*2+1;
}
}
if (t!=curIdx) {//應(yīng)該繼續(xù)向下調(diào)整台夺，就是和左孩子節(jié)點(diǎn)或者右孩子節(jié)點(diǎn)交換位置
int tem = heapArr[curIdx];
heapArr[curIdx] = heapArr[t];
heapArr[t]=tem;
setNodeP(t,maxNode);//遞歸調(diào)整
}
}
void swap(int x,int y)
{
int t;
t =heapArr[x];
heapArr[x]=heapArr[y];
heapArr[y]=t;
return;
}
void siftdown(int i)
{
int t,flag =0;
while (i*2<=max && flag==0) {
if (heapArr[i]>heapArr[2*i]) {
t = i*2;
}
else{
t=i;
}
if (i*2+1<=max) {
if (heapArr[t]>heapArr[i*2+1]) {
t=i*2+1;
}
}
if (t!=i) {
swap(t, i);
i=t;
}else{
flag =1;
}
}
}
for (int idx = max /2; idx >=1; idx --) {
setNodeP(idx, max);
}
3.排序
可以直接依次取出堆頂元素径玖，然后調(diào)整剩下的元素痴脾，使得二叉樹依舊保持堆特性，比如上面建立的是最小堆梳星，堆頂元素永遠(yuǎn)是當(dāng)前集合中最小的赞赖。僅僅排序可以依次取出，但是這樣不好冤灾，靈活性不夠
// max = sum; //每次取走最上面的元素前域，然后把最大節(jié)點(diǎn)的元素放在頂部，重新調(diào)整韵吨，使得剩余的節(jié)點(diǎn)依舊滿足最小堆的特性匿垄。
for (int i = 1; i<=sum; i++) {
int t = heapArr[1];
heapArr[1]=heapArr[max];
max--;
setNodeP(1, max);
printf("%d ",t);
}
可以通過依次調(diào)整堆的每個(gè)元素，使得完全二叉樹按照層次遍歷就可以得到有序的序列
,這樣就對于介紹的時(shí)候應(yīng)該建立最大堆归粉，然后通過調(diào)節(jié)節(jié)點(diǎn)位置稱為最小堆然后完成排序的過程了椿疗，因?yàn)樯厦娼⒌氖亲钚《选Ｋ韵旅媾判蚴菑拇蟮叫】返浚旅孢@個(gè)靈活性強(qiáng)届榄，比如當(dāng)某個(gè)元素大小改變時(shí)【笪梗可以很快的重新構(gòu)建成有序序列铝条，依然僅僅是下面的代碼靖苇。
for (int i = sum; i>1; i--) {
swap(1, i);//第一個(gè)元素和最后一個(gè)元素的位置，此時(shí)最后一個(gè)元素的最小值
setNodeP(1, i-1);//重新調(diào)整第一個(gè)元素的位置班缰，使得二叉樹仍然滿足最小堆特性贤壁。
}
for (int i=1; i<=sum; i++) {
printf("%d ",heapArr[i]);
}
堆排序的運(yùn)行時(shí)間主要是構(gòu)建堆和重建堆的反復(fù)篩選，對于每個(gè)非葉子節(jié)點(diǎn)來說最多進(jìn)行兩次比較和互換埠忘，時(shí)間復(fù)雜度為O(n)芯砸，正式排序時(shí)第i次取堆頂元素用O(log2i)的時(shí)間（完全二叉樹節(jié)點(diǎn)到根節(jié)點(diǎn)的距離是log2i + 1）,并且需要取n-1次堆頂記錄，重建堆的復(fù)雜度為nlog2n给梅。對數(shù)據(jù)原始狀態(tài)不敏感假丧，僅僅用了一個(gè)交換的臨時(shí)單元作為輔助空間。此外因?yàn)槌跏蓟瘶?gòu)建堆比較次數(shù)多动羽，所以適合數(shù)據(jù)量非常大的情況,堆排序是不穩(wěn)定的算法包帚，相當(dāng)于簡單選擇排序算法的升級(jí)。
