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

void InsertSort(int R[], int n) {int i, j, temp;for (int i = 0; i < n; i++) {temp = R[i]; //將待插入關(guān)鍵字暫存于temp中j = i - 1;//下面這個循環(huán)完成了從待排關(guān)鍵字之前得關(guān)鍵字開始掃描，如果大于待排關(guān)鍵字，則后移一位while (j >= 0 && temp < R[i]) {R[j + 1] = R[j]; ? //每個后移--j;}R[j + 1] = temp; //找到插入位置，將temp中暫存得關(guān)鍵字插入} }

?折半插入排序：每趟將一個待排序的關(guān)鍵字按照其值得大小插入到已經(jīng)排好得部分有序序列的適當(dāng)位置上，直到所有待排關(guān)鍵字都被插入到有序序列為止和直接插入得區(qū)別在于查找方式不同

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

void Shellsort(int Array[], int n){int d = n / 2;//設(shè)置起始增量while (d >= 1){//增量為1時排序結(jié)束for (int k = 0; k < d; ++k){//遍歷所有的子序for (int i = k + d; i < n; i += d){//對每個子序進(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;//縮小增量} }

冒泡排序?

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用來標(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;//如果沒有發(fā)生交換，則flag的值為0,；如果發(fā)生了交換，flag的值改為1}}if (0 == flag)//一趟排序過程中如果沒有發(fā)生關(guān)鍵字交換，則證明序列有序，排序結(jié)束return;} }

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

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

?簡單選擇類排序：選擇類排序的主要動作是“選擇”。簡單選擇采用最簡單的選擇方式，從頭至尾掃描序列，選出最小的一個關(guān)鍵字，和第一個關(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;//下面這個循環(huán)是算法的關(guān)鍵，它從序列中挑選出最小的一個關(guān)鍵字for (j = i + 1; j < n; ++j){if (R[k] > R[j])k = j;}//下面三句完成最小關(guān)鍵字與無序序列的第一個關(guān)鍵字的交換temp = R[i];R[i] = R[k];R[k] = temp;} }

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

堆排序中最關(guān)鍵的操作是將序列調(diào)整為堆。整個排序的過程就是通過不斷調(diào)整，使得不符合堆定義的完全二叉樹變?yōu)榉隙讯x的完全二叉樹堆的插入關(guān)鍵字：需要在插入結(jié)點之后保持堆的性質(zhì)，即完全二叉樹形態(tài)與父大子小性質(zhì)(以大根堆為例)，
因此需要先將要插入的結(jié)點X放在最底層的最右邊，插入后滿足完全二叉樹的特點，然后把X依次向上調(diào)整到合適位置上以滿足父大子小的性質(zhì)堆中刪除結(jié)點：刪除堆中一個結(jié)點時，原來的位置就會出現(xiàn)一個孔，填充這個孔的方法就是：
把最底層最右邊的葉子值賦給該孔并下調(diào)到合適的位置，最后把該葉子結(jié)點點刪除堆排序執(zhí)行過程描述（以大根堆為例）：
????1）從無序序列所確定的完全二叉樹的第一個非葉子結(jié)點開始，從左至右，從上至下，對每個結(jié)點進(jìn)行調(diào)整，最終得到一個大根堆?對結(jié)點的調(diào)整方法：將當(dāng)前結(jié)點（假設(shè)為A）的值與其孩子結(jié)點進(jìn)行比較，如果存在大于A的值的孩子結(jié)點。則從中挑出最大的一個與A進(jìn)行交換。當(dāng)A來到下一層的時候重復(fù)上述過程，直到A的孩子結(jié)點的值都小于A的值為止。
????2）將當(dāng)前的無序序列中的第一個關(guān)鍵字，反應(yīng)在樹的根結(jié)點（假設(shè)為B）與無序序列中的最后一個關(guān)鍵字交換（假設(shè)為C）。B進(jìn)入有序序列，達(dá)到最終位置。無序序列中的關(guān)鍵字個數(shù)減少1個，有序序列中的關(guān)鍵字個數(shù)增加1個，此時只有結(jié)點C可能不滿足堆的定義，對其進(jìn)行調(diào)整
????3)重復(fù)上述第2）步，直到無序序列中的關(guān)鍵字個數(shù)為1時結(jié)束排序

//本函數(shù)完成在數(shù)組R[Low]到R[High]的范圍內(nèi)對在位置Low上的結(jié)點進(jìn)行調(diào)整 void Sift(int R[], int Low, int High){//這里關(guān)鍵字的存儲設(shè)定為從數(shù)組下標(biāo)為1開始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+1}if (temp < R[j]){R[i] = R[j];//將R[j]調(diào)整到雙親結(jié)點的位置上i = j;j = 2 * i;//修改i和j的值，以便繼續(xù)向下調(diào)整}else break;}R[i] = temp;//被調(diào)整結(jié)點的值放入最終位置 } //堆排序函數(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é)點中的關(guān)鍵字，將其放入最終的位置temp = R[1];R[1] = R[i];R[i] = temp;Sift(R, 2, i - 1);//在減少了1個關(guān)鍵字的無序序列中進(jìn)行調(diào)整} }

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

二路歸并排序：先將整個序列分為兩半，對每一半分別進(jìn)行歸并排序，將得到兩個有序序列，然后將這兩個序列歸并成一個序列即可。

void merge(int A[], int low, int mid, int high) {int i, j, temp;for (int i = mid; i <high; ++i) { //將A[m,m+n-1]插入到A[0,m-1]中 //逐個插入temp = A[i];for (j = i - 1; j >= low && temp < A[j]; --j) { //尋找一個合適的位置A[j + 1] = A[j]; ?//元素后移}A[j + 1] = temp;} } void mergeSort(int A[], int low, int high) {if (low < high) {int mid = (low + high) / 2;mergeSort(A, low, mid);// 歸并排序前半段mergeSort(A, mid + 1, high);//歸并排序后半段merge(A, low, mid, high); ?//將數(shù)組A中l(wèi)ow到mid和mid+1到high范圍內(nèi)的兩段有序序列歸并成一段有序序列} }

?

總結(jié)

以上是生活随笔為你收集整理的天勤数据结构代码——排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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