快排源代碼

昨天看了一下午的快排，終于寫出了快排，并且測試通過，現貼出與大家共享。

[cpp] view plain?

1. #include <stdio.h>  
2. void quickSort(int a[],int left,int right);  
3. void swap(int *x,int *y);  
4. int main(){  
5.     int array[]={10,9,8,7,6,5,4,3,2,1};  
6.     quickSort(array,0,9);  
7.     int i=0;  
8.     for(i=0;i<10;i++)  
9.         printf("%d ",array[i]);  
10.     printf("\n");  
11.     return 0;  
12. }  
13. void quickSort(int a[],int left,int right){  
14.     int i=left,j=right;  
15.     int pivot=a[left];      //設最左的待排數組為基數  
16.     for(;;){  
17.         while(i<j&&a[j]>=pivot)    //j從右到左找比基數小的數  
18.             j--;  
19.         while(i<j&&a[i]<=pivot)    //i從左到右找比基數大的數  
20.             i++;  
21.         if(i<j)                    //i<j,交換找出符合條件的兩數  
22.             swap(&a[i],&a[j]);  
23.         else                       //否則第一次循環結束，i左側的數比基數都小，i右側的數比基數都大  
24.             break;  
25.     }  
26.     swap(&a[i],&a[left]);  
27.     if(left<right)            //判斷數組長度是否大于1，至少有兩數才需繼續遞歸  
28.         quickSort(a,left,i-1);  
29.     if(left<right)  
30.         quickSort(a,i+1,right);  
31. }  
32. void swap(int *x,int *y){  
33.     int temp=*x;  
34.     *x=*y;  
35.     *y=temp;  
36. }  

下列代碼是參考網上的代碼，也一并貼出

[html] view plain?

1. #include <stdio.h>  
2. void quickSort(int numbers[], int array_size);  
3. void q_sort(int numbers[], int left, int right);  
4. int main(){  
5.     int array[]={7,4,6,9,1,3,8,2,10,5};  
6.     quickSort(array,10);  
7.     int i=0;  
8.     for(i=0;i<10;i++)  
9.         printf("%d ",array[i]);  
10.     printf("\n");  
11.     return 0;  
12. }  
13. void quickSort(int numbers[], int array_size)  
14. {  
15.   q_sort(numbers, 0, array_size - 1);  
16. }  
17. void q_sort(int numbers[], int left, int right)  
18. {  
19.   int pivot, l_hold, r_hold;  
20.   l_hold = left;  
21.   r_hold = right;  
22.   pivot = numbers[left];  
23.   while (left < right)  
24.   {  
25.     while ((numbers[right] >= pivot) && (left < right))  
26.       right--;  
27.     if (left != right)  
28.     {  
29.       numbers[left] = numbers[right];  
30.       left++;  
31.     }  
32.     while ((numbers[left] <= pivot) && (left < right))  
33.       left++;  
34.     if (left != right)  
35.     {  
36.       numbers[right] = numbers[left];  
37.       right--;  
38.     }  
39.   }  
40.   numbers[left] = pivot;  
41.   pivot = left;  
42.   left = l_hold;  
43.   right = r_hold;  
44.   if (left < pivot)  
45.     q_sort(numbers, left, pivot-1);  
46.   if (right > pivot)  
47.     q_sort(numbers, pivot+1, right);  
48. }  

或者

[html] view plain?

1.  #include<stdio.h>  
2. void quicksort(int x[],int,int);  
3. int main(){  
4.   int x[100],size,i;  
5.   printf("Enter size of the array: ");  
6.   scanf("%d",&size);  
7.   printf("Enter %d elements: ",size);  
8.   for(i=0;i<size;i++)  
9.     scanf("%d",&x[i]);  
10.   quicksort(x,0,size-1);  
11.   printf("Sorted elements: ");  
12.   for(i=0;i<size;i++)  
13.     printf(" %d",x[i]);  
14.   return 0;  
15. }  
16. void quicksort(int x[],int first,int last){  
17.     int pivot,j,temp,i;  
18.      if(first<last){  
19.          pivot=first;  
20.          i=first;  
21.          j=last;  
22.          while(i<j){  
23.              while(x[i]<=x[pivot]&&i<last)  
24.                  i++;  
25.              while(x[j]>x[pivot])  
26.                  j--;  
27.              if(i<j){  
28.                  temp=x[i];  
29.                   x[i]=x[j];  
30.                   x[j]=temp;  
31.              }  
32.          }  
33.          temp=x[pivot];  
34.          x[pivot]=x[j];  
35.          x[j]=temp;  
36.          quicksort(x,first,j-1);  
37.          quicksort(x,j+1,last);  
38.     }  
39. }