常用的排序算法（C語言）

前言

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

02

冒泡排序

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

示例：

#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）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

示例：

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; //記錄最小值序號 

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

04

插入排序

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

示例：

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

int i,j,temp; 

for (i=1;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

希爾排序

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

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

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

• 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位

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

示例：

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)進行插入排序 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)用的是分治的思想，將大隊列劃分成小隊列，然后小隊列內(nèi)排序，再將排好序的小隊列組合成大隊列，步驟：

1、將劃分成兩個隊列直到不可再分為止

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

3、左隊列與右隊列合并

4、返回合并的隊列

示例：

//遞歸法實現(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

快速排序

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

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

示例：

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

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

//遞歸法實現(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)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！