排序算法

直接插入排序算法：每趟將一個(gè)待排序的關(guān)鍵字按照其值的大小插入到已經(jīng)排好的部分有序序列的適當(dāng)位置上，直到所有待排關(guān)鍵字都被插入到有序序列中為止

void InsertSort(int R[], int n)?? ?//代拍關(guān)鍵字存儲(chǔ)在R[]中，默認(rèn)為整形，個(gè)數(shù)為n {int i = 0, j = 0;int temp = 0;for (i = 1; i < n; ++i){temp = R[i];?? ?//將待插入關(guān)鍵字暫存于temp中j = i + 1;//下面這個(gè)循環(huán)完成待排關(guān)鍵字之前的關(guān)鍵字開(kāi)始掃描，如果大于待排關(guān)鍵字，則后移一位while (j >= 0 && temp < R[j]){R[j + 1] = R[j];--j;}R[j + 1] = temp;?? ?//找到插入位置，將temp中暫存的待排關(guān)鍵字插入} } //直接插入算法的時(shí)間復(fù)雜度為O(n*n)

?? ?希爾排序：希爾排序又稱之為縮小增量排序，其本質(zhì)還是插入排序，只不過(guò)是將待排序列按照某種規(guī)則分成幾個(gè)子序列
?? ?，分別對(duì)這幾個(gè)子序列進(jìn)行直接插入排序。這個(gè)規(guī)則的體現(xiàn)就是增量的選取.希爾排序的時(shí)間復(fù)雜度為O(n*logn)
?

void Shellsort(int Array[], int n) {int d = n / 2;?? ?//設(shè)置起始增量while (d >= 1)?? ?//增量為1時(shí)排序結(jié)束{for (int k = 0; k < d; ++k)?? ?//遍歷所有的子序{for (int i = k + d; i < n; i += d)?? ?//對(duì)每個(gè)子序進(jìn)行插入排序{int temp = Array[i];int j = i - d;while (j >= k && Array[j] > temp){Array[j + d] = Array[j];j -= d;}Array[j + d] = temp;}}d = d / 2;?? ?//縮小增量} } //冒泡排序：時(shí)間復(fù)雜度為O(n*n) void BubbleSort(int R[], int n)?? ??? ?//默認(rèn)待排序關(guān)鍵字為整型 {int i = 0, j = 0, flag = 0;int temp;for (int i = n - 1; i >= 1; --i){flag = 0;?? ??? ??? ?//變量flag用來(lái)標(biāo)記本堂排序是否發(fā)生了交換for (j = 0; j < i; ++j)if (R[j - 1] > R[j]){temp = R[j];R[j] = R[j - 1];R[j - 1] = temp;flag = 1;?? ?//如果沒(méi)有發(fā)生交換，則flag的值為0,；如果發(fā)生了交換，flag的值改為1}if (0 == flag)?? ?//一趟排序過(guò)程中如果沒(méi)有發(fā)生關(guān)鍵字交換，則證明序列有序，排序結(jié)束return;} }

快速排序；也是交換類的排序，它通過(guò)多次劃分操作實(shí)現(xiàn)排序。以升序?yàn)槔?#xff0c;其執(zhí)行流程可以概括為：每一趟選擇當(dāng)前所有子序列中的一個(gè)關(guān)鍵字（通常是第一個(gè)）作為樞軸，將子序列中比樞軸小的移到樞軸的前邊，比樞軸大的移動(dòng)到樞軸的后邊；當(dāng)本趟所有的子序列都被樞軸以上述規(guī)則劃分完畢后會(huì)的到新的一組更短的子序列，它們成為下一趟劃分的初始序列集。快速排序的算法思想基于分治思想的，其平均時(shí)間復(fù)雜度為O(n*logn)，最壞時(shí)間復(fù)雜度為O(n*n)
?

void QuickSort(int R[], int low, int high)?? ?//對(duì)從R[Low]到R[High]的關(guān)鍵字進(jìn)行排序 {int temp = 0;int i = low, j = high;if (low < high){temp = R[low];//下面這個(gè)循環(huán)完成了一趟排序，即數(shù)組中小于temp的關(guān)鍵字放在左邊，大于temp的關(guān)鍵字放在右邊。左邊和右邊的分界點(diǎn)就是temp的最終位置while (i < j){while (i < j && R[j] >= temp)?? ?//先從右往左掃描，找到第一個(gè)小于temp的關(guān)鍵字--j;if (i < j)?? ??? ?//這個(gè)判斷保證退出上面的while循環(huán)是因?yàn)镽[j] < temp，而不是因?yàn)?i>= j退出循環(huán)的，此步非常重要切忌將其忽略{R[i] = R[j];?? ?//放在temp左邊++i;?? ??? ??? ?//i右移一位}while (i < j && R[i] <= temp)?? ?//從右往左掃描，找到一個(gè)大于temp的關(guān)鍵字++i;if (i < j){R[j] = R[i];?? ?//放在tem的左邊--j;?? ??? ??? ?//j右移一位}}R[j] = temp;?? ?//將temp放在最終的位置上QuickSort(R, low, i - 1);?? ?//遞歸的對(duì)temp左邊的關(guān)鍵字進(jìn)行排序QuickSort(R, i + 1, high);?? ?//遞歸的對(duì)temp右邊的關(guān)鍵字進(jìn)行排序} }

? 簡(jiǎn)單選擇類排序：選擇類排序的主要?jiǎng)幼魇恰斑x擇”。簡(jiǎn)單選擇采用最簡(jiǎn)單的選擇方式，從頭至尾掃描序列，選出
最小的一個(gè)關(guān)鍵字，和第一個(gè)關(guān)鍵字交換，接著從剩下的關(guān)鍵字中繼續(xù)這種選擇和交換，最終使序列有序

void SelectSort(int R[], int n) {int i = 0, j = 0, k = 0;int temp = 0;for (i = 0; i < n; ++i){k = i;//下面這個(gè)循環(huán)是算法的關(guān)鍵，它從序列中挑選出最小的一個(gè)關(guān)鍵字for (j = i + 1; j < n; ++j){if (R[k] > R[j])k = j;}//下面三句完成最小關(guān)鍵字與無(wú)序序列的第一個(gè)關(guān)鍵字的交換temp = R[i];R[i] = R[k];R[k] = temp;} }

? 堆排序：對(duì)是一種完全二叉樹(shù),這顆二叉樹(shù)滿足：任何一個(gè)非葉結(jié)點(diǎn)的值都不大于(或小于)其左右孩子結(jié)點(diǎn)的值。若父親大孩子小，這樣的堆稱之為大頂堆；若父親小孩子大稱為小根堆。
根據(jù)堆的定義可以知道，代表堆的這顆完全二叉樹(shù)的根結(jié)點(diǎn)是最大的（或者最小的），因此將一個(gè)無(wú)序的序列調(diào)整為一個(gè)堆，就可以找到這個(gè)序列的最大值（或者最小）的值，然后將找出的值交換到這個(gè)序列的最后（或最前），這樣有序序列關(guān)鍵字增加1個(gè)，無(wú)序序列中的關(guān)鍵字減少1個(gè)，對(duì)新的無(wú)序序列重復(fù)這樣的操作，就實(shí)現(xiàn)了排序。這就是堆排序的思想
? ?堆排序中最關(guān)鍵的操作是將序列調(diào)整為堆。整個(gè)排序的過(guò)程就是通過(guò)不斷調(diào)整，使得不符合堆定義的完全二叉樹(shù)變?yōu)榉隙讯x的完全二叉樹(shù)

? 堆的插入關(guān)鍵字：需要在插入結(jié)點(diǎn)之后保持堆的性質(zhì)，即完全二叉樹(shù)形態(tài)與父大子小性質(zhì)(以大根堆為例)，因此需要先將要插入的結(jié)點(diǎn)X放在最底層的最右邊，插入后滿足完全二叉樹(shù)的特點(diǎn)，然后把X依次向上調(diào)整到合適位置上以滿足父大子小的性質(zhì)

? 堆中刪除結(jié)點(diǎn)：刪除堆中一個(gè)結(jié)點(diǎn)時(shí)，原來(lái)的位置就會(huì)出現(xiàn)一個(gè)孔，填充這個(gè)孔的方法就是：把最底層最右邊的葉子值賦給該孔并下調(diào)到合適的位置，最后把
該葉子結(jié)點(diǎn)點(diǎn)刪除堆排序執(zhí)行過(guò)程描述（以大根堆為例）：
?? ?1）從無(wú)序序列所確定的完全二叉樹(shù)的第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始，從左至右，從上至下，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行調(diào)整，最終得到一個(gè)大根堆
?? ?對(duì)結(jié)點(diǎn)的調(diào)整方法：將當(dāng)前結(jié)點(diǎn)（假設(shè)為A）的值與其孩子結(jié)點(diǎn)進(jìn)行比較，如果存在大于A的值的孩子結(jié)點(diǎn)，則從中挑出最大的一個(gè)與A進(jìn)行交換。當(dāng)A來(lái)到
?? ?下一層的時(shí)候重復(fù)上述過(guò)程，直到A的孩子結(jié)點(diǎn)的值都小于A的值為止。
?? ?2）將當(dāng)前的無(wú)序序列中的第一個(gè)關(guān)鍵字，反應(yīng)在樹(shù)的根結(jié)點(diǎn)（假設(shè)為B）與無(wú)序序列中的最后一個(gè)關(guān)鍵字交換（假設(shè)為C）。B進(jìn)入有序序列，達(dá)到最終位置。
?? ?無(wú)序序列中的關(guān)鍵字個(gè)數(shù)減少1個(gè)，有序序列中的關(guān)鍵字個(gè)數(shù)增加1個(gè)，此時(shí)只有結(jié)點(diǎn)C可能不滿足堆的定義，對(duì)其進(jìn)行調(diào)整
?? ?3)重復(fù)上述第2）步，直到無(wú)序序列中的關(guān)鍵字個(gè)數(shù)為1時(shí)結(jié)束排序
代碼如下：

//本函數(shù)完成在數(shù)組R[Low]到R[High]的范圍內(nèi)對(duì)在位置Low上的結(jié)點(diǎn)進(jìn)行調(diào)整 void Sift(int R[], int Low, int High)//這里關(guān)鍵字的存儲(chǔ)設(shè)定為從數(shù)組下標(biāo)為1開(kāi)始 {int i = Low, j = 2 * i;?? ?//R[j]是R[i]的左孩子int temp = R[i];while (j <= High){if (j < High && R[j] < R[j + 1])?? ?//若右孩子較大，則把j指向右孩子++j;?? ??? ?//j變?yōu)?2*i+1if (temp < R[j]){R[i] = R[j];?? ?//將R[j]調(diào)整到雙親結(jié)點(diǎn)的位置上i = j;j = 2 * i;?? ?//修改i和j的值，以便繼續(xù)向下調(diào)整}else break;}R[i] = temp;?? ??? ??? ?//被調(diào)整結(jié)點(diǎn)的值放入最終位置 } //堆排序函數(shù) void HeapSort(int R[], int n) {int i = 0;int temp = 0;for (i = n / 2; i >= 1; --i)?? ??? ?//初始化堆Sift(R, i, n);for (i = n; i >= 2; --i)?? ??? ??? ??? ?//進(jìn)行n-1次循環(huán)完成堆排序{//下面三句換出了根結(jié)點(diǎn)中的關(guān)鍵字，將其放入最終的位置temp = R[1];R[1] = R[i];R[i] = temp;Sift(R, 2, i - 1);?? ??? ?//在減少了1個(gè)關(guān)鍵字的無(wú)序序列中進(jìn)行調(diào)整}

?? ?堆排序算法所需的空間復(fù)雜度為O(1)，這是它相對(duì)于歸并排序的優(yōu)點(diǎn)。時(shí)間復(fù)雜度在任何情況下均為O(n*logn)，這是它相對(duì)于快速排序的最大優(yōu)點(diǎn)，?快速排序最壞的時(shí)間復(fù)雜度為O(n*n)。
?? ?堆排序適用場(chǎng)景是關(guān)鍵字?jǐn)?shù)目特別多的情況下，典型的例子是從10000個(gè)關(guān)鍵字選出前10個(gè)最小的。這種情況下用堆排序最好。如果關(guān)鍵字?jǐn)?shù)目較少，則不建議使用堆排序
?? ?//STL中已經(jīng)寫(xiě)好了堆排序，一般如果是自己在實(shí)踐中需要用的是由直接調(diào)用下面兩句即可
??

?make_heap(_First, _Last, _Comp);?? ?//默認(rèn)是建立最大堆的。對(duì)int類型，可以在第三個(gè)參數(shù)傳入greater<int>()得到最小堆。sort_heap(_First, _Last);?? ??? ??? ?//排序之后就不再是一個(gè)合法的heap了make_heap(b, b + 10 ,greater<int> ());?? ?//建立小根堆sort_heap(b, b + 10, greater<int>());?? ?//從大到小進(jìn)行排序make_heap()建堆的時(shí)候，默認(rèn)是大根堆，第三個(gè)參數(shù)用greater<T>會(huì)變成小根堆；sort_heap()排序的時(shí)候，默認(rèn)是從小到大，但是第三個(gè)參數(shù)用greater<T>會(huì)變成從大到小并且sort_heap的第三個(gè)參數(shù)要和make_heap的第三個(gè)參數(shù)一致，否則程序運(yùn)行時(shí)會(huì)報(bào)錯(cuò)//上面這兩個(gè)函數(shù)原型為：template <class RandomAccessIterator>void make_heap (RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void make_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp );template<class _RanIt> inlinevoid sort_heap(_RanIt _First, _RanIt _Last){?? ?// order heap by repeatedly popping, using operator<_STD sort_heap(_First, _Last, less<>());}

*/

總結(jié)

以上是生活随笔為你收集整理的排序算法（天勤数据结构高分笔记）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。