俗话说得好：排序千万种，方便第一种，排序不规范，找bug两行泪。上次写了一篇关于插入排序和冒泡排序的博文，这次再来介绍一下选择排序法和快速排序法。
选择排序法，顾名思义就是将需要的数选择出来，再放到需要的地方。例如有一个数组[1，5，4，6，7，3，2]，对这个数组进行选择排序的话，大致可以归纳为以下几个步骤：
假设第i个元素即为最小的数据，采用temp变量记录其下标依次遍历从i+1开始的后面的元素，并与tempi相比较，若小于temp则记录当前元素的下标步骤二遍历完成之后，将temp下标的元素与步骤一中的元素进行交换，即实现了将最小的数据选择出来并挪到前面的过程。重复步骤一、二、三采用伪代码表示如下：
for(int i = 0; i < arr.size(); ++i){ int temp = i; //假设第i个元素为最小数值 for(int j = i + 1; j < arr.size(); ++j){ if(*(arr + temp < *(arr + j)) //第j个和第i个作比较 temp = j; //找到第i个元素后面比第i个元素要小的元素 } if(temp == i)) continue; //如果第i个元素就是最小元素，则进行下一轮循环 else swap((arr + temp), (arr + i)); //将第i个元素和第temp个元素交换位置，进行下一轮循环代码实现如下：
#include<iostream> /* 交换函数，通过指针交换两个地址的值 @param 待交换值1 @param 带交换值2 */ template<typename T> void swap(T* value1, T* value2) { T temp = *value1; *value1 = *value2; *value2 = temp; } /* #采用泛型，可传入任意需要比较的类型 @param 待排序的数组 @param 待排序数组的长度 */ template<typename T> void selectSort(T arr[], size_t len) { for (unsigned int i = 0; i < len - 1; ++i) { int temp = i; for (unsigned int j = i + 1; j < len; ++j) { if(*(arr + temp) >= *(arr + j)) temp = j; } if(*(arr + temp) == *(arr + i)) continue; else swap((arr + temp), (arr + i)); } }输出结果测试： 那么问题来了，该算法的时间复杂度和空间复杂度分别是多少呢？很明显的是空间复杂度为O(1)。时间复杂度为O(n²)。选择排序法相比于冒泡和插入排序法，选择排序的交换次数会有明显的减少，其最多的交换次数为n - 1次。
不论是冒泡排序，插入排序还是选择排序，其时间复杂度都是O(n²)。对于消耗的时间来说，并没有非常明显的改善。为了解决这一问题，快速排序——qsort应运而生。
快速排序法的基本思想：
先找一个基准数（一般为待排序数组的第一个值），同时设置两个指针，一个指向待排数组的最左元素（第一个），一个指向待排数组最右侧（最后一个元素）移动右侧指针将小于基准数的元素移至左侧。此时基准数的位置发生了变化移动左侧指针将大于基准数的元素移至右侧。此时基准数的位置也发生了变化重复步骤2，3直至左侧指针和右侧指针指向同一个位置。这样一趟结束后，基准点会将所有的元素分为左右两部分，再分别对左右两部分重复1，2，3，4步骤即可得到有序数组。如下图所示，先找出一个基准数（图中的3），经过第一轮移动后，待排数组被拆成了两块，再分别对左右两块作同样的排序。依此类推，便可以实现快速排序算法了。 基于上述思路，快速排序法可以采用递归法来实现，关键则是要找到每一轮循环后其基准元素所在的下标，然后将其分为两段，再进行快速排序。其伪代码可描述为：
int getRefIndex(T arr[], unsigned int left, unsigned int right){ T temp = *(arr + left); //此时的基准元素等于arr[0]，即arr[left] for(;left != right;){ while(low < high && *(arr + right) <= temp)) right--; //一直循环，找到右侧小于基准元素的数据 //找到后，需要将其与temp交换，考虑到此时的temp就是arr[left]，因此可直接覆盖 arr[left] = arr[right]; while(low < high && *(arr + left) > temp)) left++; //一直循环，找到左侧大于基准元素的数据 //同样的找到之后需要交换，但是此时考虑到右侧的值即arr[right]已经写入arr[left]中了，因此可直接覆盖。 arr[right] = arr[left]; } //for循环结束后即left == right，因此可以直接将temp放入 arr[right] = temp; //arr[left] = temp也行 return left; //return right也行。上面的步骤完成后，只需要递归调用即可了。其伪代码如下：
void myQsort(T arr[], unsigned int left, unsigned int right){ if(left < right){ int refIndex = getRefIndex(arr, left, right); //获取第一次基准元素的下标 myQsort(arr, left refIndex - 1); //对左半部分递归 myQsort(arr, refIndex + 1, right); //对右半部分递归 }根据上面的思路，我们可以写出以下测试代码：
#pragma once #include<iostream> using namespace std; template<typename T> int getRefIndex(T arr[], unsigned int left, unsigned int right) { int temp = *(arr + left); for (; left < right;) { while (left < right && *(arr + right) >= *(arr + left)) //从右侧开始找，找到比左侧大的数 --right; *(arr + left) = *(arr + right); while (left < right && *(arr + left) <= *(arr + right)) //从左侧开始找，找到比右侧小的数 ++left; *(arr + right) = *(arr + left); }//循环结束后，left == right成立 *(arr + left) = temp; return left; } template<typename T> void myQsort(T arr[], unsigned int left, unsigned int right) { if (left < right) { int refIndex = getRefIndex(arr, left, right); myQsort(arr, left, refIndex - 1); //递归左侧 myQsort(arr, refIndex + 1, right); //递归右侧 } }测试结果如下： 快速排序的时间复杂度平均为O(nlgn)相比于其他的O(n²)来的要小，但是这种递归方式的空间复杂度将不再是O(1)而是O(nlgn)。这就是典型的以空间换时间的案例。
