算法進修入門之應用C說話完成各年夜根本的排序算法。本站提示廣大學習愛好者：（算法進修入門之應用C說話完成各年夜根本的排序算法）文章只能為提供參考，不一定能成為您想要的結果。以下是算法進修入門之應用C說話完成各年夜根本的排序算法正文
起首來看一下排序算法的一些相干概念：
1、穩固排序和非穩固排序
簡略地說就是一切相等的數經由某種排序辦法後，仍能堅持它們在排序之前的絕對順序，我們就說這類排序辦法是穩固的。反之，就長短穩固的。
好比：一組數排序前是a1,a2,a3,a4,a5，個中a2=a4，經由某種排序後為a1,a2,a4,a3,a5，則我們說這類排序是穩固的，由於a2排序前在a4的後面，排序後它照樣在a4的後面。假設釀成a1,a4,a2,a3,a5就不是穩固的了。
2、內排序和外排序
在排序進程中，一切須要排序的數都在內存，並在內存中調劑它們的存儲次序，稱為內排序；
在排序進程中，只要部門數被調入內存，並借助內存調劑數在外存中的寄存次序排序辦法稱為外排序。
3、算法的時光龐雜度和空間龐雜度
所謂算法的時光龐雜度，是指履行算法所須要的盤算任務量。
一個算法的空間龐雜度，普通是指履行這個算法所須要的內存空間。
接上去我們現實來看幾年夜排序算法的詳細C說話完成：
冒泡排序 (Bubble Sort)
假如序列是從小到年夜分列好的，那末隨意率性兩個相鄰元素，都應當知足a[i-1] <= a[i]的關系。在冒泡排序時，我們從右向左遍歷數組，比擬相鄰的兩個元素。假如兩個元素的次序是錯的，那末就交流這兩個元素。假如兩個元素的次序是准確的，則不做交流。經由一次遍歷，我們可以包管最小的元素(泡泡)處於最右邊的地位。
經由一次遍歷，冒泡排序其實不能包管一切的元素曾經依照從小到年夜的分列好。是以，我們須要從新從右向左遍歷數組元素，並停止冒泡排序。這一次遍歷，我們不消斟酌最左真個元素。然後持續停止最多為n-1次的遍歷。
假如某次遍歷進程中，元素都沒有產生交流，那末解釋數組曾經排序好，可以中斷停滯排序。最壞的情形是在肇端數組中，最年夜的元素位於最右邊，那末冒泡算法必需經由n-1次遍歷能力將數組分列好，而不克不及提早完成排序。
/*By Vamei*/
/*swap the neighbors if out of order*/
void bubble_sort(int a[], int ac)
{
/*use swap*/
int i,j;
int sign;
for (j = 0; j < ac-1; j++) {
sign = 0;
for(i = ac-1; i > j; i--)
{
if(a[i-1] > a[i]) {
sign = 1;
swap(a+i, a+i-1);
}
}
if (sign == 0) break;
}
}
拔出排序 (Insertion Sort)
假定在重生報到的時刻，我們將重生依照身高排好隊(也就是排序)。假如這時候有一位先生參加，我們將該邏輯學生參加到隊尾。假如這邏輯學生比後面的先生低，那末就讓該先生和後面的先生交流地位。這邏輯學生終究會換到應在的地位。這就是拔出排序的根本道理。
關於肇端數組來講，我們以為最後，有一位先生，也就是最右邊的元素(i=0)，組成一個有序的部隊。
隨後有第二個先生(i=1)參加部隊，第二邏輯學生交流到應在的地位；隨後第三個先生參加部隊，第三邏輯學生交流到應在的地位…… 當n個先生都參加部隊時，我們的排序就完成了。
/*By Vamei*/
/*insert the next element
into the sorted part*/
void insert_sort(int a[], int ac)
{
/*use swap*/
int i,j;
for (j=1; j < ac; j++)
{
i = j-1;
while((i>=0) && (a[i+1] < a[i]))
{
swap(a+i+1, a+i);
i--;
}
}
}
選擇排序 (Selection Sort)
排序的終究成果：任何一個元素都不年夜於位於它左邊的元素 (a[i] <= a[j], if i <= j)。所以，在有序序列中，最小的元素排在最左的地位，第二小的元素排在i=1的地位…… 最年夜的元素排在最初。
選擇排序是先找到肇端數組中最小的元素，將它交流到i=0；然後尋覓剩下元素中最小的元素，將它交流到i=1的地位…… 直到找到第二年夜的元素，將它交流到n-2的地位。這時候，全部數組的排序完成。
/*By Vamei*/
/*find the smallest of the rest,
then append to the sorted part*/
void select_sort(int a[], int ac)
{
/*use swap*/
int i,j;
int min_idx;
for (j = 0; j < ac-1; j++)
{
min_idx = j;
for (i = j+1; i < ac; i++)
{
if (a[i] < a[min_idx])
{
min_idx = i;
}
}
swap(a+j, a+min_idx);
}
}
希爾排序 （Shell Sort）
我們在冒泡排序中提到，最壞的情形產生在年夜的元素位於數組的肇端。這些位於數組肇端的年夜元素須要屢次遍歷，能力交流到隊尾。如許的元素被稱為烏龜(turtle)。
烏龜元素的緣由在於，冒泡排序老是相鄰的兩個元素比擬並交流。所以每次從右向左遍歷，年夜元素只能向右挪動一名。(小的元素位於隊尾，被稱為兔子(rabbit)元素，它們可以很快的交流到隊首。)
希爾排序是以更年夜的距離來比擬和交流元素，如許，年夜的元素在交流的時刻，可以向右挪動不止一個地位，從而更快的挪動烏龜元素。好比，可以將數組分為4個子數組（i=4k, i=4k+1, i=4k+2, i=4k+3），對每一個子數組停止冒泡排序。好比子數組i=0，4，8，12...。此時，每次交流的距離為4。
完成對四個子數組的排序後，數組的次序其實不必定能分列好。希爾排序會赓續減小距離，從新構成子數組，並對子數組冒泡排序…… 當距離減小為1時，就相當於對全部數組停止了一次冒泡排序。隨後，數組的次序就分列好了。
希爾排序不止可以合營冒泡排序，還可以合營其他的排序辦法完成。
/*By Vamei*/
/*quickly sort the turtles at the tail of the array*/
void shell_sort(int a[], int ac)
{
int step;
int i,j;
int nsub;
int *sub;
/* initialize step */
step = 1;
while(step < ac) step = 3*step + 1;
/* when step becomes 1, it's equivalent to the bubble sort*/
while(step > 1) {
/* step will go down to 1 at most */
step = step/3 + 1;
for(i=0; i<step; i++) {
/* pick an element every step,
and combine into a sub-array */
nsub = (ac - i - 1)/step + 1;
sub = (int *) malloc(sizeof(int)*nsub);
for(j=0; j<nsub; j++) {
sub[j] = a[i+j*step];
}
/* sort the sub-array by bubble sorting.
It could be other sorting methods */
bubble_sort(sub, nsub);
/* put back the sub-array*/
for(j=0; j<nsub; j++) {
a[i+j*step] = sub[j];
}
/* free sub-array */
free(sub);
}
}
}
Shell Sorting依附於距離(step)的拔取。一個罕見的選擇是將本次距離設置為前次距離的1/1.3。見參考書本。
合並排序 (Merge Sort)
假如我們要將一副撲克依照數字年夜小排序。此前曾經有兩小我分離將個中的一半排好次序。那末我們可以將這兩堆撲克向上放好，假定小的牌在下面。此時，我們將看到牌堆中最上的兩張牌。
我們取兩張牌中小的那張掏出放在手中。兩個牌堆中又是兩張牌裸露在最下面，持續取小的那張放在手中…… 直到一切的牌都放動手中，那末整副牌就排好次序了。這就是合並排序。
上面的完成中，應用遞歸：
/*By Vamei*/
/*recursively merge two sorted arrays*/
void merge_sort(int *a, int ac)
{
int i, j, k;
int ac1, ac2;
int *ah1, *ah2;
int *container;
/*base case*/
if (ac <= 1) return;
/*split the array into two*/
ac1 = ac/2;
ac2 = ac - ac1;
ah1 = a + 0;
ah2 = a + ac1;
/*recursion*/
merge_sort(ah1, ac1);
merge_sort(ah2, ac2);
/*merge*/
i = 0;
j = 0;
k = 0;
container = (int *) malloc(sizeof(int)*ac);
while(i<ac1 && j<ac2) {
if (ah1[i] <= ah2[j]) {
container[k++] = ah1[i++];
}
else {
container[k++] = ah2[j++];
}
}
while (i < ac1) {
container[k++] = ah1[i++];
}
while (j < ac2) {
container[k++] = ah2[j++];
}
/*copy back the sorted array*/
for(i=0; i<ac; i++) {
a[i] = container[i];
}
/*free space*/
free(container);
}
疾速排序 (Quick Sort)
我們仍然斟酌依照身高給先生排序。在疾速排序中，我們隨意挑出一個先生，以該先生的身高為參考(pivot)。然後讓比該先生低的站在該先生的左邊，剩下的站在該先生的右邊。
很顯著，一切的先生被分紅了兩組。該先生左邊的先生的身高都年夜於該先生右邊的先生的身高。
我們持續，在低身高先生組隨意挑出一個先生，將低身高組的先生分為兩組(很低和不那末低)。異樣，將高先生組也分為兩組(不那末高和很高)。
如斯持續細分，直到分組中只要一個先生。當一切的分組中都只要一個先生時，則排序完成。
鄙人面的完成中，應用遞歸:
/*By Vamei*/
/*select pivot, put elements (<= pivot) to the left*/
void quick_sort(int a[], int ac)
{
/*use swap*/
/* pivot is a position,
all the elements before pivot is smaller or equal to pvalue */
int pivot;
/* the position of the element to be tested against pivot */
int sample;
/* select a pvalue.
Median is supposed to be a good choice, but that will itself take time.
here, the pvalue is selected in a very simple wayi: a[ac/2] */
/* store pvalue at a[0] */
swap(a+0, a+ac/2);
pivot = 1;
/* test each element */
for (sample=1; sample<ac; sample++) {
if (a[sample] < a[0]) {
swap(a+pivot, a+sample);
pivot++;
}
}
/* swap an element (which <= pvalue) with a[0] */
swap(a+0,a+pivot-1);
/* base case, if only two elements are in the array,
the above pass has already sorted the array */
if (ac<=2) return;
else {
/* recursion */
quick_sort(a, pivot);
quick_sort(a+pivot, ac-pivot);
}
}
幻想的pivot是采取分組元素中的中位數。但是尋覓中位數的算法須要另行完成。也能夠隨機拔取元素作為pivot，隨機拔取也須要另行完成。為了輕便，我每次都采取中央地位的元素作為pivot。
堆排序 (Heap Sort)
堆(heap)是罕見的數據構造。它是一個有優先級的隊列。最多見的堆的完成是一個無限定操作的Complete Binary Tree。這個Complete Binary Tree堅持堆的特征，也就是父節點(parent)年夜於子節點(children)。是以，堆的根節點是一切堆元素中最小的。堆界說有拔出節點和刪除根節點操作，這兩個操作都堅持堆的特征。
我們可以將無序數組組成一個堆，然後赓續掏出根節點，終究組成一個有序數組。
堆的更具體描寫請浏覽參考書目。
上面是堆的數據構造，和拔出節點和刪除根節點操作。你可以很便利的構建堆，並掏出根節點，組成有序數組。
/* By Vamei
Use an big array to implement heap
DECLARE: int heap[MAXSIZE] in calling function
heap[0] : total nodes in the heap
for a node i, its children are i*2 and i*2+1 (if exists)
its parent is i/2 */
void insert(int new, int heap[])
{
int childIdx, parentIdx;
heap[0] = heap[0] + 1;
heap[heap[0]] = new;
/* recover heap property */
percolate_up(heap);
}
static void percolate_up(int heap[]) {
int lightIdx, parentIdx;
lightIdx = heap[0];
parentIdx = lightIdx/2;
/* lightIdx is root? && swap? */
while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
/* swap */
swap(heap + lightIdx, heap + parentIdx);
lightIdx = parentIdx;
parentIdx = lightIdx/2;
}
}
int delete_min(int heap[])
{
int min;
if (heap[0] < 1) {
/* delete element from an empty heap */
printf("Error: delete_min from an empty heap.");
exit(1);
}
/* delete root
move the last leaf to the root */
min = heap[1];
swap(heap + 1, heap + heap[0]);
heap[0] -= 1;
/* recover heap property */
percolate_down(heap);
return min;
}
static void percolate_down(int heap[]) {
int heavyIdx;
int childIdx1, childIdx2, minIdx;
int sign; /* state variable, 1: swap; 0: no swap */
heavyIdx = 1;
do {
sign = 0;
childIdx1 = heavyIdx*2;
childIdx2 = childIdx1 + 1;
if (childIdx1 > heap[0]) {
/* both children are null */
break;
}
else if (childIdx2 > heap[0]) {
/* right children is null */
minIdx = childIdx1;
}
else {
minIdx = (heap[childIdx1] < heap[childIdx2]) ?
childIdx1 : childIdx2;
}
if (heap[heavyIdx] > heap[minIdx]) {
/* swap with child */
swap(heap + heavyIdx, heap + minIdx);
heavyIdx = minIdx;
sign = 1;
}
} while(sign == 1);
}
總結
除下面的算法，還有諸如Bucket Sorting, Radix Sorting觸及。我會在將來完成了相干算法以後，彌補到這篇文章中。相干算法的時光龐雜度剖析可以參考書目中找到。我本身也做了粗拙的剖析。假如博客 園能支撐數學公式的顯示，我就把本身的剖析進程貼出來，用於引玉。
下面的各個代碼是我本身寫的，只停止了很簡略的測試。假如有訛奪，先感謝你的斧正。
最初，上文頂用到的交流函數為：
/* By Vamei */
/* exchange the values pointed by pa and pb*/
void swap(int *pa, int *pb)
{
int tmp;
tmp = *pa;
*pa = *pb;
*pb = tmp;
}
幾種排序算法的比擬和選擇
1. 拔取排序辦法須要斟酌的身分：
(1) 待排序的元素數量n；
(2) 元素自己信息量的年夜小；
(3) 症結字的構造及其散布情形；
(4) 說話對象的前提，幫助空間的年夜小等。
2. 一些建議：
(1) 若n較小(n <= 50)，則可以采取直接拔出排序或直接選擇排序。因為直接拔出排序所需的記載挪動操作較直接選擇排序多，因此當記載自己信息量較年夜時，用直接選擇排序較好。
(2) 若文件的初始狀況已按症結字根本有序，則選用直接拔出或冒泡排序為好。
(3) 若n較年夜，則應采取時光龐雜度為O(nlog2n)的排序辦法：疾速排序、堆排序或合並排序。疾速排序是今朝基於比擬的外部排序法中被以為是最好的辦法。
(4) 在基於比擬排序辦法中，每次比擬兩個症結字的年夜小以後，僅僅湧現兩種能夠的轉移，是以可以用一棵二叉樹來描寫比擬剖斷進程，由此可以證實：當文件的n個症結字隨機散布時，任何借助於"比擬"的排序算法，至多須要O(nlog2n)的時光。
(5) 當記載自己信息量較年夜時，為防止消耗年夜量時光挪動記載，可以用鏈表作為存儲構造。
