快速排序应该算是在面试笔试中最常用的算法了,各位面试官都非常喜欢。排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,其中的思想也是用了分治法和递归的思想。示例代码上传到:https://github.com/chenyufeng1991/QuickSort
算法的基本思想是:
(1)先从数列中取出一个数作为基准数(常常选第一个数);
(2)分区过程,比这个数大的数放到它的右边,小于或等于的数全放到它的左边;
(3)再对左右区间重复第二步,直到每个区间只有一个数位置,即左边界下标等于右边界下标;
简化描述为:
1.i= L, j=R,基准数即为a[i],保存起来;
2.j--,由后向前找比它小的数,找到后将此数放到a[i]中;
3.i++,由前向后找比它大的数,找到后将此数填入到a[j]中;
4.递归执行2,3两步,直到i==j,最后将基准数填入a[i]中;
具体代码实现如下:
// // main.c // QuickSort // // Created by chenyufeng on 16/1/27. // Copyright © 2016年 chenyufengweb. All rights reserved. // #include <stdio.h> int *quickSort(int arr[],int l,int r); void quickSort02(int *arr,int l,int r); int main(int argc, const char * argv[]) { int numArr[5] = {3,6,0,9,4}; //使用指针返回数组,返回的其实是数组的头指针; /** * 使用返回指针; */ // int *retArr; // retArr = quickSort(numArr, 0, 4); // for (int i = 0; i < 5; i++) { // //取数组值 // printf("%d ",*(retArr + i)); // } /** * 直接传递引用,比较方便; */ quickSort02(numArr, 0, 4); for (int i = 0; i < 5; i++) { printf("%d ",numArr[i]); } } int *quickSort(int arr[],int l,int r){ //当左右指针相等的时候直接返回; if (l < r) { //此时的x就是基准值; int i = l,j = r,x = arr[l]; //下面的while循环表示一次分治,也就是进行一次排序; while (i < j) { //先从基准值右侧找出小于基准的值; while (i < j && arr[j] >= x) { j--; } if (i < j) { //交换顺序,i++; arr[i++] = arr[j]; } //从基准值左侧找出大于基准的值; while (i < j && arr[i] < x) { i++; } if (i < j) { //交换顺序,j--; arr[j--] = arr[i]; } } //把基准值放入arr[i]位置; arr[i] = x; //递归,左右两侧分别进行快排; quickSort(arr, l, i - 1); quickSort(arr, i + 1, r); } return arr; } void quickSort02(int *arr,int l,int r){ //当左右指针相等的时候直接返回; if (l < r) { //此时的x就是基准值; int i = l,j = r,x = arr[l]; //下面的while循环表示一次分治,也就是进行一次排序; while (i < j) { //先从基准值右侧找出小于基准的值; while (i < j && arr[j] >= x) { j--; } if (i < j) { //交换顺序,i++; arr[i++] = arr[j]; } //从基准值左侧找出大于基准的值; while (i < j && arr[i] < x) { i++; } if (i < j) { //交换顺序,j--; arr[j--] = arr[i]; } } //把基准值放入arr[i]位置; arr[i] = x; //递归,左右两侧分别进行快排; quickSort(arr, l, i - 1); quickSort(arr, i + 1, r); } }</stdio.h>