歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

快速排序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)。快速排序是種不穩定排序。
Copyright © Linux教程網 All Rights Reserved