快速排序Linux下c 实现
这次、给出快速排序的实现，主要代码如下：
1、排序头文件：quickSort.h
#ifndef QUICKSORT_H#define QUICKSORT_Hextern 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:mainmain:main.o quickSort.o gcc -o main main.o quickSort.omain.o:main.c gcc -c main.cquickSort.o:quickSort.c gcc -c quickSort.cclean: @echo "start cleanning..." -rm main *.o @echo "completed clean".PHONY:clean
6、编译：
[root@localhost quickSort]$ makegcc -c main.cgcc -c quickSort.cgcc -o main main.o quickSort.o
如果一切顺利，降看到可执行文件：main，执行大致如下：
[root@localhost quickSort]$ ./main Input array length:10Get 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
快速排序最差时间复杂度是：О(n2)，最优时间复杂度：О(nlogn)，平均时间复杂度：О(nlogn)。快速排序是种不稳定排序。