C語言，動(dòng)態(tài)展示經(jīng)典排序算法

4 快速排序

1. 選取第一個(gè)數(shù)為基準(zhǔn)
2. 將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面
3. 對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)

代碼：

    

     void QuickSort(vector& v, int low, int high) {
 if (low >= high) // 結(jié)束標(biāo)志
 return;
 int first = low; // 低位下標(biāo)
 int last = high; // 高位下標(biāo)
 int key = v[first]; // 設(shè)第一個(gè)為基準(zhǔn)

 while (first < last)
 {
 // 將比第一個(gè)小的移到前面
 while (first < last && v[last] >= key)
 last--;
 if (first < last)
 v[first++] = v[last];

 // 將比第一個(gè)大的移到后面
 while (first < last && v[first] <= key)
 first++;
 if (first < last)
 v[last--] = v[first];
 }
 //
 v[first] = key;
 // 前半遞歸
 QuickSort(v, low, first - 1);
 // 后半遞歸
 QuickSort(v, first + 1, high);
}

    

5 堆排序

1. 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；
2. 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
3. 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。

代碼：

    

     #include 
#include 
using namespace std;

// 堆排序：（最大堆，有序區(qū)）。從堆頂把根卸出來放在有序區(qū)之前，再恢復(fù)堆。

void max_heapify(int arr[], int start, int end) {
 //建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)
 int dad = start;
 int son = dad * 2 + 1;
 while (son <= end) { //若子節(jié)點(diǎn)在范圍內(nèi)才做比較
 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個(gè)子節(jié)點(diǎn)指標(biāo)，選擇最大的
 son++;
 if (arr[dad] > arr[son]) //如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完成，直接跳出函數(shù)
 return;
 else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)與孫節(jié)點(diǎn)比較
 swap(arr[dad], arr[son]);
 dad = son;
 son = dad * 2 + 1;
 }
 }
}

void heap_sort(int arr[], int len) {
 //初始化，i從最后一個(gè)父節(jié)點(diǎn)開始調(diào)整
 for (int i = len / 2 - 1; i >= 0; i--)
 max_heapify(arr, i, len - 1);
 //先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換，再從新調(diào)整(剛調(diào)整的元素之前的元素)，直到排序完成
 for (int i = len - 1; i > 0; i--) {
 swap(arr[0], arr[i]);
 max_heapify(arr, 0, i - 1);
 }
}

int main() {
 int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
 int len = (int) sizeof(arr) / sizeof(*arr);
 heap_sort(arr, len);
 for (int i = 0; i < len; i++)
 cout << arr[i] << ' ';
 cout << endl;
 return 0;
}

    

6 歸并排序

代碼：

    

     void print(int a[], int n){
 for(int j= 0; j cout< }
 cout<}

//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
 int j,k;
 for(j=m+1,k=i; i<=m && j <=n ; ++k){
 if(r[j] < r[i]) rf[k] = r[j++];
 else rf[k] = r[i++];
 }
 while(i <= m) rf[k++] = r[i++];
 while(j <= n) rf[k++] = r[j++];
 print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{
 int len = 1;
 ElemType *q = r ;
 ElemType *tmp ;
 while(len < lenght) {
 int s = len;
 len = 2 * s ;
 int i = 0;
 while(i+ len  Merge(q, rf, i, i+ s-1, i+ len-1 ); //對等長的兩個(gè)子表合并
 i = i+ len;
 }
 if(i + s < lenght){
 Merge(q, rf, i, i+ s -1, lenght -1); //對不等長的兩個(gè)子表合并
 }
 tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時(shí)，仍從q 歸并到rf
 }
}


int main(){
 int a[10] = {2，3,4，5,15,19,26,27,36,38,44,46,47,48,50};
 int b[10];
 MergeSort(a, b, 15);
 print(b,15);
 cout<<"結(jié)果：";
 print(a,10);
}

    

7 希爾排序

1. 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列個(gè)數(shù)k，對序列進(jìn)行k 趟排序；
3. 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。

代碼：

    

     void shell_sort(T array[], int length) {
 int h = 1;
 while (h < length / 3) {
 h = 3 * h + 1;
 }
 while (h >= 1) {
 for (int i = h; i < length; i++) {
 for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
 std::swap(array[j], array[j - h]);
 }
 }
 h = h / 3;
 }
}

    

8 計(jì)數(shù)排序

• 計(jì)數(shù)排序基于一個(gè)假設(shè)，待排序數(shù)列的所有數(shù)均為整數(shù)，且出現(xiàn)在（0，k）的區(qū)間之內(nèi)。
• 如果 k（待排數(shù)組的最大值） 過大則會引起較大的空間復(fù)雜度，一般是用來排序 0 到 100 之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。
• 計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

1. 找出待排序的數(shù)組中最大和最小的元素；
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)；
3. 對所有的計(jì)數(shù)累加（從 C 中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）；
4. 向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 C[i] 項(xiàng)，每放一個(gè)元素就將 C[i] 減去 1；

代碼：

    

     #include 
#include 
#include 

using namespace std;

// 計(jì)數(shù)排序
void CountSort(vector& vecRaw, vector& vecObj)
{
 // 確保待排序容器非空
 if (vecRaw.size() == 0)
 return;

 // 使用 vecRaw 的最大值 + 1 作為計(jì)數(shù)容器 countVec 的大小
 int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
 vector vecCount(vecCountLength, 0);

 // 統(tǒng)計(jì)每個(gè)鍵值出現(xiàn)的次數(shù)
 for (int i = 0; i < vecRaw.size(); i++)
 vecCount[vecRaw[i]]++;
 
 // 后面的鍵值出現(xiàn)的位置為前面所有鍵值出現(xiàn)的次數(shù)之和
 for (int i = 1; i < vecCountLength; i++)
 vecCount[i] += vecCount[i - 1];

 // 將鍵值放到目標(biāo)位置
 for (int i = vecRaw.size(); i > 0; i--) // 此處逆序是為了保持相同鍵值的穩(wěn)定性
 vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}

int main()
{
 vector vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
 vector vecObj(vecRaw.size(), 0);

 CountSort(vecRaw, vecObj);

 for (int i = 0; i < vecObj.size(); ++i)
 cout << vecObj[i] << " ";
 cout << endl;

 return 0;
}

    

9 桶排序

1. 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
2. 尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對應(yīng)的桶子去。
3. 對每個(gè)不是空的桶子進(jìn)行排序。
4. 從不是空的桶子里把項(xiàng)目再放回原來的序列中。

代碼：

    

     function bucketSort(arr, bucketSize) {
 if (arr.length === 0) {
 return arr;
 }
 
 var i;
 var minValue = arr[0];
 var maxValue = arr[0];
 for (i = 1; i < arr.length; i++) {
 if (arr[i] < minValue) {
 minValue = arr[i]; // 輸入數(shù)據(jù)的最小值
 } else if (arr[i] > maxValue) {
 maxValue = arr[i]; // 輸入數(shù)據(jù)的最大值
 }
 }
 
 // 桶的初始化
 var DEFAULT_BUCKET_SIZE = 5; // 設(shè)置桶的默認(rèn)數(shù)量為5
 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
 var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
 var buckets = new Array(bucketCount);
 for (i = 0; i < buckets.length; i++) {
 buckets[i] = [];
 }
 
 // 利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中
 for (i = 0; i < arr.length; i++) {
 buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
 }
 
 arr.length = 0;
 for (i = 0; i < buckets.length; i++) {
 insertionSort(buckets[i]); // 對每個(gè)桶進(jìn)行排序，這里使用了插入排序
 for (var j = 0; j < buckets[i].length; j++) {
 arr.push(buckets[i][j]);
 }
 }
 
 return arr;
}

    

10 基數(shù)排序

1. 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
2. arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
3. 對radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）

代碼：

    

     int maxbit(int data[], int n) //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)
{
 int maxData = data[0]; ///< 最大數(shù)
 /// 先求出最大數(shù)，再求其位數(shù)，這樣有原先依次每個(gè)數(shù)判斷其位數(shù)，稍微優(yōu)化點(diǎn)。
 for (int i = 1; i < n; ++i)
 {
 if (maxData < data[i])
 maxData = data[i];
 }
 int d = 1;
 int p = 10;
 while (maxData >= p)
 {
 //p *= 10; // Maybe overflow
 maxData /= 10;
 ++d;
 }
 return d;
/* int d = 1; //保存最大的位數(shù)
 int p = 10;
 for(int i = 0; i < n; ++i)
 {
 while(data[i] >= p)
 {
 p *= 10;
 ++d;
 }
 }
 return d;*/
}
void radixsort(int data[], int n) //基數(shù)排序
{
 int d = maxbit(data, n);
 int *tmp = new int[n];
 int *count = new int[10]; //計(jì)數(shù)器
 int i, j, k;
 int radix = 1;
 for(i = 1; i <= d; i++) //進(jìn)行d次排序
 {
 for(j = 0; j < 10; j++)
 count[j] = 0; //每次分配前清空計(jì)數(shù)器
 for(j = 0; j < n; j++)
 {
 k = (data[j] / radix) % 10; //統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)
 count[k]++;
 }
 for(j = 1; j < 10; j++)
 count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個(gè)桶
 for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
 {
 k = (data[j] / radix) % 10;
 tmp[count[k] - 1] = data[j];
 count[k]--;
 }
 for(j = 0; j < n; j++) //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中
 data[j] = tmp[j];
 radix = radix * 10;
 }
 delete []tmp;
 delete []count;
}
? 2020 GitHub, Inc.