快速排序Linux下C 实现

快速排序Linux下C 实现

这次、给出快速排序的实现，主要代码如下：

1、排序头文件：quickSort.h

1. #ifndef QUICKSORT_H  
2. #define QUICKSORT_H  
3. extern void quickSort(int *pArr, int length);  
4. #endif  

2、排序源文件：quickSort.c 

1. #include "quickSort.h"   
2.   
3. void quick_Sort(int * pArr, int left, int right)  
4. {  
5.         if(left >= right)   
6.         {  
7.                 return;  
8.         }  
9.         int k = *(pArr+left);  
10.         int l,r;  
11.         l=left;  
12.         r=right;  
13.         while(left < right)  
14.         {  
15.                 while(*(pArr+right)>k && right> left)  
16.                 {  
17.                         right--;  
18.                 }  
19.                 if(left!=right)  
20.                 {  
21.                         *(pArr+left)=*(pArr+right);  
22.                         left++;  
23.                 }  
24.                 while(*(pArr+left)<k && left < right)  
25.                 {  
26.                         left++;  
27.                 }  
28.                 if(left!=right)  
29.                 {  
30.                         *(pArr+right)=*(pArr+left);  
31.                         right--;  
32.                 }  
33.         }  
34.         *(pArr+left)=k;  
35.   
36.         if(l < left-1)  
37.         {  
38.                 quick_Sort(pArr, l, left-1);  
39.         }  
40.         if(r > left+1)  
41.         {  
42.                 quick_Sort(pArr, left+1, r);  
43.         }  
44. }  
45.   
46. void quickSort(int *pArr, int length)  
47. {  
48.         quick_Sort(pArr, 0, length-1);  
49. }  

3、main头文件： main.h

1. #ifndef MAIN_H  
2. #define MAIN_H  
3. #include<stdio.h>  
4. #include "quickSort.h"  
5. int main(void);  
6. void showArr(const int *pArr, const int length);  
7. void initRandomArr(int *pArr, const int length);  
8. #endif  

4、main源文件：main.c 

1. #include "main.h"  
2.   
3. int main(void)  
4. {  
5.         printf("Input array length:\n");  
6.         int length;  
7.         scanf("%d", &length);  
8.         if(length<0)  
9.         {  
10.                 printf("Array length must be larger 0\n");  
11.                 return 1;  
12.         }  
13.         int arr[length];  
14.         initRandomArr(arr, length);  
15.         printf("Get random array :\n");  
16.         showArr(arr, length);  
17.         quickSort(arr, length);  
18.         printf("quick sort result:\n");  
19.         showArr(arr, length);  
20.         return 0;  
21. }  
22. void showArr(const int *pArr, const int length)  
23. {  
24.         int i;  
25.         for(i=0; i<length; i++)  
26.         {  
27.                 printf("%d ", *(pArr+i));  
28.         }  
29.         printf("\n");  
30. }  
31. void initRandomArr(int *pArr, const int length)  
32. {  
33.         int i;  
34.         srand(time(NULL));  
35.         for(i=0; i< length; i++)  
36.         {  
37.                 *(pArr+i)=rand()%1000;  
38.         }  
39. }  

5、Makefile文件：

1. all:main  
2. main:main.o quickSort.o  
3.         gcc -o main main.o quickSort.o  
4. main.o:main.c  
5.         gcc -c main.c  
6. quickSort.o:quickSort.c  
7.         gcc -c quickSort.c  
8. clean:  
9.         @echo "start cleanning..."  
10.         -rm main *.o  
11.         @echo "completed clean"  
12. .PHONY:clean  

6、编译：

1. [root@localhost quickSort]$ make  
2. gcc -c main.c  
3. gcc -c quickSort.c  
4. gcc -o main main.o quickSort.o  

如果一切顺利，降看到可执行文件：main，执行大致如下：

1. [root@localhost quickSort]$ ./main   
2. Input array length:  
3. 10  
4. Get random array :  
5. 261 350 755 768 500 405 585 127 534 518   
6. quick sort result:  
7. 127 261 350 405 500 518 534 585 755 768   

快速排序最差时间复杂度是：О(n²)，最优时间复杂度：О(nlogn)，平均时间复杂度：О(nlogn)。快速排序是种不稳定排序。