本文共 2109 字，大约阅读时间需要 7 分钟。

C++ 快速排序 个人笔记

快速排序的代码实现

源代码

#include 
   
    /******************************函数参数: arr - 数组名*          begin - 开始遍历的数组下标*          end - 最后一个遍历的数组下标**函数作用: 在begin 到end 区间内 让arr[begin]*          这个元素移到左边小于arr[begin]*	       右边大于arr[begin]的位置上去**函数返回值: 如果begin < end 就返回arr[begin]这个数据*            现在所在的数组下标else return -2;*******************************/int quickMethod(int * arr, int begin,int end) {	int  middleNum = arr[begin];//miuddleNum 保存arr[begin]这个元素	int i = begin; //i 保存开始遍历的数组下标	int j = end; //j 这个遍历区间的最后一个数组下标	//if(begin< end)在这里应该是多于的 如果begin>end 都进不来这个函数	if (begin < end) {		//先从最里面的循环看		//重复循环一下过程 直到i ==j 循环结束		while (i < j) {			//第一次外层循环时			//只要i
    
      middleNum) {					arr[j--] = arr[i];					break;				}				else {					i++;				}			}		}		//此时i和j指向同一个元素,而这个元素是可以被覆盖的		arr[i] = middleNum;		return i;	}	else {		return -2;	}}/******************************函数参数: arr - 数组名*          begin - 开始遍历的数组下标*          end - 最后一个遍历的数组下标**函数作用: 将arr进行快速排序**函数返回值: 无*******************************/void quickSort(int* arr, int begin, int end) {	int index = -1;//index 保存基数下标	if (begin < end) {		index = quickMethod(arr, begin, end);		if (index == -2) {			exit(-2);		}		//index 这个下标以左递归再进行快速排序		quickSort(arr, begin, index - 1);		//index 这个下标以右递归再进行快速排序		quickSort(arr, index + 1, end);	}}int main(void) {	int test[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };	int len = sizeof(test) / sizeof(test[0]);	quickSort(test,0,len-1);	for (int i = 0; i < len; i++) {		printf("%d\t", test[i]);	}	return 0;}
    
   

代码的测试

快速排序的原理(个人理解)

如果看不懂,下面还有我老师的图文讲解

以升序排列（从小到大排列为例)

1、在一组待排序的数据中首先找任意一个元素当基准值，虽说是任意但你不知道这组数据有多少个，容易越界，最好选第一个元素或最后一个元素)。

定义二个变量 i指向第一个元素的下标，j指向最后一个元素的下标。

假如是选的是第一个元素当基准值，

2、然后从j开始往前遍历找到比这个基准值小的数据（j–直到比这个基准值小的数据结束循环），比这个基准值小的数据（j下标中的数据)赋值到当前i下标的位置上，然后i++;让i指向下一个数组下标 ,这个i数组下标中的元素就是小于基准值的 而j这个下标中的元素是可以被覆盖的,相当于一个坑,需要填起来。

3、从i下标开始往后遍历比这个基准值大的的数据(i++直到比这个基准值大的数据结束循环)比这个基准值大的的数据(i下标)赋值到当前j下标的位置上(坑);这个j下标中的元素就是大于基准值的，而i这个下标中的元素是可以被覆盖的,相当于一个坑,需要填起来。

4.不断循环2-3步骤(直到i<j)循环结束;

5、此时i == j ；i下标或j下标中的元素就是最后一个坑,用保存的基准值赋值到这个位置上，这个位置左边就是小于这个基准值右边是大于基准值的（但不一定是有序的）

6、再利用分治手法 以 index(基准值的位置)为界分成二组数据再进行1-5的步骤

转载地址：http://ubyki.baihongyu.com/