图片源于网络
快速排序
快速排序（Quick Sort）是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法思想
-
从数列中挑出一个元素，称为 "基准"（pivot）
-
分割（partition）操作:重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。
-
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
-
快速排序是基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：
-
分解:
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r] -
解决:
通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。 -
合并:
将排序好的子数组A[p ..q-1]和A[q+1 ..r]合并
-
图-快速排序示例图
上图中，演示了快速排序的处理过程：
-
初始状态为一组无序的数组：{2,4,5,1,3}
-
经过以上操作步骤后，完成了第一次的排序，得到新的数组：{1,2,5,4,3}
-
新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。
-
因为2已经在数组中找到了合适的位置，所以不用再动。
-
2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。
-
2右边的数组{5,4,3},设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。
范例代码
#pragma mark --- 快速排序
/**
快速排序
@param array 需要排序的Array
@param left 初始索引
@param right 最后一位索引
*/
+ (void)quickSort:(NSMutableArray *)array left:(int)left right:(int)right
{
if(array == nil || array.count == 0 || left >= right){
NSLog(@"注意快速排序条件");
return;
}
// 以最左边的数(left)为基准
int base = left;
NSNumber *prmt = array[base];
// //取中值
// int middle = left + (right - left)/2;
// NSNumber *prmt = array[middle];
int i = left;
int j = right;
/**
while是循环流程控制，使用的标准格式为
while(表达式)
{
循环语句体；
}
说明：①while循环的表达式是循环进行的条件，用作循环条件的表达式中一般至少包括一个能够改变表达式的变量，这个变量称为循环变量
②当表达式的值为真（非零）时，执行循环体；为假（0）时，则循环结束
③当循环体不需要实现任何功能时，可以用空语句作为循环体
④对于循环变量的初始化应在while语句之前进行，可以通过适当方式给循环变量赋初值
*/
//开始排序，使得left<prmt 同时right>prmt
while (i < j) {
// while ([array[j] intValue] > [prmt intValue]) {
//该行与下一行作用相同
// j 从右至左移动(j--) 直到找到一个小于[prmt intValue]的数停下来
while ([array[j] compare:prmt] == NSOrderedDescending) {
j--;
}
// while ([array[i] intValue] < [prmt intValue]) {
//该行与下一行作用相同
/**
i 从左至右移动(i++) 直到找到一个大于[prmt intValue]的数停下来
*/
while ([array[i] compare:prmt] == NSOrderedAscending) {
i++;
}
//如果i与j未相遇 交换其数据
if(i < j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
//i 与j 各移动一位 进入下一循环
i++;
j--;
}
NSLog(@"快速排序排序中:%@",array);
}
//第一轮排序完成 将数组拆成 A[p ..q-1] <= A[q] <= A[q+1 ..r] 模式的两个数组 递归
/**
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。递归有直接递归和间接递归
•直接递归：函数在执行过程中调用本身。
•间接递归：函数在执行过程中调用其它函数再经过这些函数调用本身。
•递归算法有四个特性：
（1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；
（2）子问题在规模上比原问题小，或更接近终止条件；
（3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；
（4）子问题的解应能组合为整个问题的解。
*/
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
if (left < j) {
[self quickSort:array left:left right:j];
}
// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
if (right > i) {
[self quickSort:array left:i right:right];
}
}
算法分析
-
快速排序的算法性能
快速排序的算法性能
-
时间复杂度
-
快速排序涉及到递归调用。其递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n)
-
最优情况下时间复杂度
快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；
此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；
快速排序最优的情况下时间复杂度为：O( N*log N )
-
最差情况下时间复杂度
最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
这种情况时间复杂度就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
快速排序最差的情况下时间复杂度为：O( N^2 )
-
平均时间复杂度
快速排序平均时间复杂度为：O( N*log N )
-
-
空间复杂度
快速排序在每次分割的过程中，需要 1 个空间存储基准值。
最优的情况下空间复杂度为：O(log N) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( N ) ；退化为冒泡排序的情况 -
算法稳定性
在快速排序中，相等元素可能会因为分区而交换顺序，如: 当待排序元素类似[6,1,3,7,3]且基准元素为6时，经过分区，形成[1,3,3,6,7],两个3的相对位置发生了改变，所是快速排序是一种不稳定排序。
网友评论