提出
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序,它有一种比较重要的思想——分治思想。大致可以描述为,确保一组序列中存在一个特别的数据,其左边的数据都比他大(小),右边的数据都比它小(大),那么可以将这个数作为基准数,在其左边和右边分别再次确保一个数满足同等关系,直到区间大小为1,则排序完成。
时间复杂度
O(N*logN)
步骤
- 选取基准数
- 以基准数为中心点进行分区,左边分区比基准数小(大),右边分区比基准数大(小)。
- 每个分区递归完成上述规则,直到分区大小为1。
代码实现
快速排序实现方式多样,这里对本实现方式做简要介绍。
在这里为实现代码简洁,选取第一个数作为基准数,如需设置其他位置的数作为基准数,则只需要将该位置的数与第一个数交换位置即可。
初始情况:
15, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987
首先保存基准数的值( tmp = arr[s] ),然后从最右边查找第一个小于等于基准数的值,并将该值保存到基准值的位置(基准值已保存,所以可以直接将该值覆盖,红色覆盖蓝色),并将基准值位置向右偏移一位(s++),由于基准值以第一个数开始,则可以理解为将小值往右边扔。执行完成结果应当是这样:
8, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987
此时可以看到有两个数值8,我们可以理解为,可以在右边的8头上随便动土~
因此,我们开始从基准值位置开始向右移动,直到找到第一个比基准值大的数。然后去欺负右边的8,直接覆盖掉他,然后右边界限减1(e–)。数组此时变为:
8, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 423, 987
可以很直观的发现,此时有两个423,话不多说,从右边开始找小于基准值的数,盘他。
8, 3, 12, 23, 32, 13, 6, 3256, 5567, 12, 423, 987
这样,我们始终保持一个可改变的数值去容纳查找到的符合规定的值,直到基准值到达右界限( s >= e )并将基准值赋予该位置( arr[s] = tmp )。则满足基准值左右分治条件(左边小与基准值,右边大于基准值)。结果为:
8, 3, 12, 6, 13, 15, 32, 3256, 5567, 23, 432, 987
最后,划分左右分区,实行递归即可。
/*快速排序 *C/C++ */ #include <iostream> using namespace std; int quick_sort( int *arr, int start, int end ) { int s = start, e = end;//记录分区信息 //swap(arr[s],arr[(s+e)]/2); int tmp = arr[s];//保存基准值 if ( s >= e ) { return 0; } while ( s < e ) { while ( s < e && arr[e] )//从右向左查找第一个小于等于基准值的数 { if ( arr[e--] <= tmp ) { arr[s++] = arr[++e];//将该值往区间最右边移动 break; } } while ( s < e && arr[s] ) //从左向右查找第一个大于基准值的数 { if ( arr[s++] > tmp ) { arr[e--] = arr[--s];//将该值往区间最左边移动 break; } } } arr[s] = tmp;//将基准值填入对应位置 quick_sort( arr, start, s - 1 );//递归左分区 quick_sort( arr, s + 1, end );//递归右分区 return 0; } int main() { int arr[] = {15, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987}; int end = sizeof( arr ) / sizeof( arr[0] ) - 1; int start = 0;//此处以第一个数作为基准数,若以其他数(如中间数)作为基准数,则应实现并打开修改swap注释。 quick_sort( arr, start, end ); while ( start <= end ) { cout << arr[start++] << endl; } return 0; }