常用的排序算法（C語(yǔ)言）

前言

排序是數(shù)據(jù)處理中經(jīng)常運(yùn)用的一種重要運(yùn)算，排序的功能是將一個(gè)數(shù)據(jù)元素（記錄）的任意序列，重新排列成一個(gè)按照一個(gè)規(guī)則有序的序列。常用的排序算法我們要熟練掌握。

02

冒泡排序

冒泡排序（英語(yǔ)：Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序（如從大到小、首字母從A到Z）錯(cuò)誤就把他們交換過(guò)來(lái)。

示例：

#include void bubble_sort(int arr[], int len) { 

int i, j, temp; 

for (i = 0; i < len - 1; i++) 

for (j = 0; j < len - 1 - i; j++) 

if (arr[j] > arr[j + 1]) { 

temp = arr[j]; 

arr[j] = arr[j + 1]; 

arr[j + 1] = temp; }}

int main() { 

int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 }; 

int len = (int) sizeof(arr) / sizeof(*arr); 

bubble_sort(arr, len); 

int i; 

for (i = 0; i < len; i++) printf("%d ", arr[i]); 

return 0;

}

03

選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢。

示例：

void swap(int *a,int *b) { 

int temp = *a; *a = *b; 

*b = temp;}

void selection_sort(int arr[], int len) { 

int i,j;  

for (i = 0 ; i < len - 1 ; i++)  { 

int min = i; 

for (j = i + 1; j < len; j++) //走訪未排序列 

if (arr[j] < arr[min]) //找到目前最小值 

min = j; //記錄最小值序號(hào) 

swap(&arr[min], &arr[i]); //做交換 }}

04

插入排序

插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

示例：

void insertion_sort(int arr[], int len){ 

int i,j,temp; 

for (i=1;i//從第二個(gè)元素開(kāi)始 temp = arr[i]; for (j=i;j>0 && arr[j-1]>temp;j--) arr[j] = arr[j-1]; //大于temp的值后移 

arr[j] = temp; //temp放入序列 }}

05

希爾排序

希爾排序，也稱(chēng)遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率

• 但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

希爾排序先將待排記錄序列分割成為若干子序列分別進(jìn)行插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。

示例：

void shell_sort(int arr[], int len) { 

int gap, i, j; int temp; for (gap = len >> 1; 

gap > 0; gap = gap >> 1)//分子序列 for (i = gap; i < len; i++) { 

//序列內(nèi)進(jìn)行插入排序 temp = arr[i]; 

for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) 

arr[j + gap] = arr[j]; arr[j + gap] = temp; }}

06

歸并排序

歸并排序應(yīng)用的是分治的思想，將大隊(duì)列劃分成小隊(duì)列，然后小隊(duì)列內(nèi)排序，再將排好序的小隊(duì)列組合成大隊(duì)列，步驟：

1、將劃分成兩個(gè)隊(duì)列直到不可再分為止

2、小隊(duì)列內(nèi)排序

3、左隊(duì)列與右隊(duì)列合并

4、返回合并的隊(duì)列

示例：

//遞歸法實(shí)現(xiàn)

void merge_sort_recursive(int arr[], int reg[], int start, int end) { i

f (start >= end) return; 

int len = end - start, mid = (len >> 1) + start; 

int start1 = start, end1 = mid; 

int start2 = mid + 1, end2 = end; 

merge_sort_recursive(arr, reg, start1, end1); 

merge_sort_recursive(arr, reg, start2, end2); 

int k = start; 

while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; 

while (start1 <= end1) reg[k++] = arr[start1++]; 

while (start2 <= end2) reg[k++] = arr[start2++]; 

for (k = start; k <= end; k++) arr[k] = reg[k];}

void merge_sort(int arr[], const int len) { 

int reg[len];

merge_sort_recursive(arr, reg, 0, len - 1);

}

07

快速排序

快速排序的基本思想是：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。一趟快速排序的具體過(guò)程可描述為：從待排序列中任意選取一個(gè)記錄(通常選取第一個(gè)記錄)作為基準(zhǔn)值，然后將記錄中關(guān)鍵字比它小的記錄都安置在它的位置之前，將記錄中關(guān)鍵字比它大的記錄都安置在它的位置之后。這樣，以該基準(zhǔn)值為分界線，將待排序列分成的兩個(gè)子序列。

一趟快速排序的具體做法為：設(shè)置兩個(gè)指針low和high分別指向待排序列的開(kāi)始和結(jié)尾，記錄下基準(zhǔn)值baseval(待排序列的第一個(gè)記錄)，然后先從high所指的位置向前搜索直到找到一個(gè)小于baseval的記錄并互相交換，接著從low所指向的位置向后搜索直到找到一個(gè)大于baseval的記錄并互相交換，重復(fù)這兩個(gè)步驟直到low=high為止

示例：

void swap(int *x, int *y) { 

int t = *x; *x = *y; *y = t;}

//遞歸法實(shí)現(xiàn)

void quick_sort_recursive(int arr[], int start, int end) { 

if (start >= end) return; 

int mid = arr[end]; 

int left = start, right = end - 1; 

while (left < right) { 

while (arr[left] < mid && left < right) left++; 

while (arr[right] >= mid && left < right) right--; 

swap(&arr[left], &arr[right]); } 

if (arr[left] >= arr[end]) swap(&arr[left], &arr[end]); 

else left++; 

if (left) quick_sort_recursive(arr, start, left - 1); 

quick_sort_recursive(arr, left + 1, end);}

void quick_sort(int arr[], int len) { quick_sort_recursive(arr, 0, len - 1);}

免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！