C言語疾速排序算法及代碼

疾速排序是對冒泡法排序的一種改良。
疾速排序算法 的根本思惟是：將所要停止排序的數(shù)分為閣下兩個局部，個中一局部的一切數(shù)據(jù)都比別的一 局部的數(shù)據(jù)小，然后將所分得的兩局部數(shù)據(jù)停止異樣的劃分，反復履行以上的劃分操作，直 到一切要停止排序的數(shù)據(jù)變?yōu)橛行驗橹埂?/span>
能夠僅依據(jù)根本思惟對疾速排序的看法并不深，接下來以對n個無序數(shù)列A[0], A[1]…, A[n-1]采取疾速排序辦法停止升序陳列為例停止解說。
(1)界說兩個變量low和high，將low、high辨別設置為要停止排序的序列的肇端元素和最初一個元素的下標。第一次，low和high的取值辨別為0和n-1，接下來的每次取值由劃分失掉的序列肇端元素和最初一個元素的下標來決議。
(2)界說一個變量key，接下來以key的取值為基準將數(shù)組A劃分為閣下兩個局部，通 常，key值為要停止排序序列的第一個元素值。第一次的取值為A[0]，今后毎次取值由要劃 分序列的肇端元素決議。
(3)從high所指向的數(shù)組元素開端向左掃描，掃描的同時將下標為high的數(shù)組元素順次與劃分基準值key停止比擬操作，直到high不大于low或找到第一個小于基準值key的數(shù)組元素，然后將該值賦值給low所指向的數(shù)組元素，同時將low右移一個地位。
(4)假如low仍然小于high，那么由low所指向的數(shù)組元素開端向右掃描，掃描的同時將下標為low的數(shù)組元素值順次與劃分的基準值key停止比擬操作，直到low不小于high或找到第一個大于基準值key的數(shù)組元素，然后將該值賦給high所指向的數(shù)組元素，同時將high左移一個地位。
(5)反復步調(3) (4)，直到low的植不小于high為止，這時勝利劃分后失掉的閣下兩局部辨別為A[low……pos-1]和A[pos+1……h(huán)igh]，個中，pos下標所對應的數(shù)組元素的值就是停止劃分的基準值key，所以在劃分完畢時還要將下標為pos的數(shù)組元素賦值 為 key。
(6)將劃分失掉的閣下兩局部A[low……pos-1]和A[pos+1……h(huán)igh]持續(xù)采取以上操作步調停止劃分，直到失掉有序序列為止。
為了可以加深讀者的了解，接下來經(jīng)過一段代碼來理解疾速排序的詳細完成辦法。

			#include <stdio.h> #include <stdlib.h> #define N 6 int partition(int arr[], int low, int high){ int key; key = arr[low]; while(low<high){ while(low <high && arr[high]>= key ) high--; if(low<high) arr[low++] = arr[high]; while( low<high && arr[low]<=key ) low++; if(low<high) arr[high--] = arr[low]; } arr[low] = key; return low; } void quick_sort(int arr[], int start, int end){ int pos; if (start<end){ pos = partition(arr, start, end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); } return; } int main(void){ int i; int arr[N]={32,12,7, 78, 23,45}; printf("排序前 \n"); for(i=0;i<N;i++) printf("%d\t",arr[i]); quick_sort(arr,0,N-1); printf("\n 排序后 \n"); for(i=0; i<N; i++) printf("%d\t", arr[i]); printf ("\n"); system("pause"); return 0; }

運轉后果：

排序前
32    12    7    78    23    45
排序后
7    12    23    32    45    78

在下面的代碼中，依據(jù)后面引見的步調一步步完成了疾速排序算法。接下來經(jīng)過表示圖來演示第一次劃分操作。
在第一次劃分操作中，先輩行初始設置，key的值是停止劃分的基準，其值為要劃分數(shù) 組的第一個元素值，在下面的排序序列中為第一個元素值32，同時將low設置為要排序數(shù)組中第一個元素的下標，第一次排序操作時其值為0，將high設置為要排序序列最初一個 元素的下標，在下面的排序序列中其第一次取值為5。先將下標為high的數(shù)組元素與key停止比擬，因為該元素值大于key，因而high向左挪動一個地位持續(xù)掃描。因為接下來的值為 23，小于key的值，因而將23賦值給下標為low所指向的數(shù)組元素。接下來將low右移一 個地位，將low所指向的數(shù)組元素的值與key停止比擬，由干接下來的12、7都小于key， 因而low持續(xù)右移掃描，直至下標low所指向的數(shù)組元素的值為78即大于key為止，將78賦值給下標為high所指向的數(shù)組元素，同時將high左移一個地位。接下因由于low不再小于high，劃分完畢。需求留意的是，在停止劃分的進程中，多是將掃描的值與key的值停止比照，假如小于key，那么將該值賦值給數(shù)組中的別的一個元素，而該元素的值并沒有改動。 從圖中可以看出這一點，所以需求在劃分的最初將作為劃分基準的key值賦值給下標為 pos的數(shù)組元素，這個元素不再介入接下來的劃分操作。

第一次劃分操作

第一輪劃分完畢后，失掉了閣下兩局部序列A[0]、A[1]、A[2]和A[4]、A[5]，持續(xù)進 行劃分，即對毎輪劃分后失掉的兩局部序列持續(xù)劃分，直至失掉有序序列為止。