這次、給出快速排序的實現,主要代碼如下:
1、排序頭文件:quickSort.h
- #ifndef QUICKSORT_H
- #define QUICKSORT_H
- extern void quickSort(int *pArr, int length);
- #endif
2、排序源文件:quickSort.c
- #include "quickSort.h"
-
- void quick_Sort(int * pArr, int left, int right)
- {
- if(left >= right)
- {
- return;
- }
- int k = *(pArr+left);
- int l,r;
- l=left;
- r=right;
- while(left < right)
- {
- while(*(pArr+right)>k && right> left)
- {
- right--;
- }
- if(left!=right)
- {
- *(pArr+left)=*(pArr+right);
- left++;
- }
- while(*(pArr+left)<k && left < right)
- {
- left++;
- }
- if(left!=right)
- {
- *(pArr+right)=*(pArr+left);
- right--;
- }
- }
- *(pArr+left)=k;
-
- if(l < left-1)
- {
- quick_Sort(pArr, l, left-1);
- }
- if(r > left+1)
- {
- quick_Sort(pArr, left+1, r);
- }
- }
-
- void quickSort(int *pArr, int length)
- {
- quick_Sort(pArr, 0, length-1);
- }
3、main頭文件: main.h
- #ifndef MAIN_H
- #define MAIN_H
- #include<stdio.h>
- #include "quickSort.h"
- int main(void);
- void showArr(const int *pArr, const int length);
- void initRandomArr(int *pArr, const int length);
- #endif
4、main源文件:main.c
- #include "main.h"
-
- int main(void)
- {
- printf("Input array length:\n");
- int length;
- scanf("%d", &length);
- if(length<0)
- {
- printf("Array length must be larger 0\n");
- return 1;
- }
- int arr[length];
- initRandomArr(arr, length);
- printf("Get random array :\n");
- showArr(arr, length);
- quickSort(arr, length);
- printf("quick sort result:\n");
- showArr(arr, length);
- return 0;
- }
- void showArr(const int *pArr, const int length)
- {
- int i;
- for(i=0; i<length; i++)
- {
- printf("%d ", *(pArr+i));
- }
- printf("\n");
- }
- void initRandomArr(int *pArr, const int length)
- {
- int i;
- srand(time(NULL));
- for(i=0; i< length; i++)
- {
- *(pArr+i)=rand()%1000;
- }
- }
5、Makefile文件:
- all:main
- main:main.o quickSort.o
- gcc -o main main.o quickSort.o
- main.o:main.c
- gcc -c main.c
- quickSort.o:quickSort.c
- gcc -c quickSort.c
- clean:
- @echo "start cleanning..."
- -rm main *.o
- @echo "completed clean"
- .PHONY:clean
6、編譯:
- [root@localhost quickSort]$ make
- gcc -c main.c
- gcc -c quickSort.c
- gcc -o main main.o quickSort.o
如果一切順利,降看到可執行文件:main,執行大致如下:
- [root@localhost quickSort]$ ./main
- Input array length:
- 10
- Get random array :
- 261 350 755 768 500 405 585 127 534 518
- quick sort result:
- 127 261 350 405 500 518 534 585 755 768
快速排序最差時間復雜度是:О(n²),最優時間復雜度:О(nlogn),平均時間復雜度:О(nlogn)。快速排序是種不穩定排序。