C语言快速排序 | Eternal_zttz

C语言快速排序

快速排序;基本思路:

  1. 从当前参加排序的元素中任选一个元素作为分界元素,与当前参加排序的那些元素进行比较.

  2. 凡是小于分界元素的元素都移到分界元素的前面,凡是大于分界元的元素都移到分界元素的后面。

  3. 分界元素将当前参加排序的元素分成前后两部分,而分界元素处在排序的最终位置。

  4. 然后,分别对这两部分中大小大于1的部分重复上述过程直到排序结束
    时间复杂度为:O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#define SWAP(a,b) {int t = a;a =b;b =t;}
void quicksort(int a[],int left,int right){
if(left>=right)
return ;
int key = a[left];
int i = left,j = right;
while(i<j){
while(i<j&&a[j]>=key)
j--;
a[i] = a[j];
while(i<j&&a[i]<=key)
i++;
a[j] = a[i];
}
a[i] =key;
quicksort(a, left, i-1);
quicksort(a, i+1, right);
}
int main(){
int n;
while(~scanf("%d",&n)){
int num[n];
for (int i =0 ;i<n;i++)
scanf("%d",&num[i]);
quicksort(num,0,n-1);
for (int i = 0;i<n;i++)
printf("%d ",num[i]);
printf("\n");
}
}

程序输入:

1
2
9
1 5 6 8 4 3 2 9 15

程序输出:

1
1 2 3 4 5 6 8 9 15


-------------The End-------------