用C語言解釋快速排序技術。
排序是將元素按升序(或降序)排列的過程。
排序型別
C語言 提供五種排序技術,如下所示:
快速排序
它是一種分治演算法。
- 步驟1 - 從陣列中選擇一個元素,稱為樞軸元素。
- 步驟2 - 將未排序的陣列元素分成兩個陣列。
- 步驟3 - 如果值小於樞軸元素的值,則進入第一個子陣列;其餘大於樞軸元素的值進入第二個子陣列。
考慮下面的例子,其中
- P是樞軸元素。
- L是左指標。
- R是右指標。
元素是6, 3, 7, 2, 4, 5。
現在,
- 樞軸位於固定位置。
- 所有左側元素都小於樞軸。
- 右側元素都大於樞軸。
- 現在,將陣列分成兩個子陣列:左部分和右部分。
- 對左分割槽應用快速排序。
現在,
- 樞軸位於固定位置。
- 所有左側元素都小於且已排序。
- 右側元素都大於且已排序。
- 最終排序列表是合併兩個子陣列的結果:2, 3, 4, 5, 6, 7
示例
以下是使用快速排序技術對元素進行排序的C程式:
#include<stdio.h> void quicksort(int number[25],int first,int last){ int i, j, pivot, temp; if(first<last){ pivot=first; i=first; j=last; while(i<j){ while(number[i]<=number[pivot]&&i<last) i++; while(number[j]>number[pivot]) j--; if(i<j){ temp=number[i]; number[i]=number[j]; number[j]=temp; } } temp=number[pivot]; number[pivot]=number[j]; number[j]=temp; quicksort(number,first,j-1); quicksort(number,j+1,last); } } int main(){ int i, count, number[25]; printf("How many elements are u going to enter?: "); scanf("%d",&count); printf("Enter %d elements: ", count); for(i=0;i<count;i++) scanf("%d",&number[i]); quicksort(number,0,count-1); printf("Order of Sorted elements: "); for(i=0;i<count;i++) printf(" %d",number[i]); return 0; }
輸出
執行上述程式後,會產生以下輸出:
How many elements are u going to enter?: 10 Enter 10 elements: 2 3 5 7 1 9 3 8 0 4 Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9
廣告