iOS开发中会用到的排序实现
2017-07-17 本文已影响472人
咖啡凯
排序概述
所谓排序，就是根据排序码的递增或者递减顺序把数据元素依次排列起来，使一组任意排列的元素变为一组按其排序码线性有序的元素。常用的内部排序算法，包括插入排序(直接插入排序，希尔排序)、选择排序(直接选择排序，堆排序)、交换排序(冒泡排序，快速排序)、归并排序、分配排序(基数排序)。一般地，我们衡量一个算法的指标包括：
- 时间复杂度：在排序的过程中需要比较和交换的次数
- 空间复杂度：在排序过程中需要的辅助存储空间
- 稳定性： 算法的实现是否可以保证排序后相同元素的初始顺序，只要算法存在一种可以实现可以保证这种特征，那么该算法就是稳定的
- 内部排序、外部排序：在排序过程中元素是否完全在内存中
1、直接插入排序
思想：当插入第i(i>=1)个元素时，前面的V[0],...,V[i-1]个元素已经有序。这时，将第i个元素和前i-1个元素V[i-1],...,V[0]依次比较，找到插入的位置即将V[i]插入，同时原来位置上的元素向后顺移。
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100, nil];
// 时间复杂度O(n^2)
// 控件复杂度O(1)
// 稳定性： 稳定
// 内部排序
for (int i = 0; i < dataArr.count; i++) {
for (int j = i; j > 0; j--) {
if ([dataArr[j] intValue] < [dataArr[j - 1] intValue]) {
[dataArr exchangeObjectAtIndex:j withObjectAtIndex:j-1];
}
}
}
NSLog(@"直接插入排序结果----%@",dataArr);
2、希尔排序
思想：假设待排序的元素共 N 个元素，首先取一个整数 i<n 作为间隔，将全部元素分为间隔为 i 的 i 个子序列并对每个子序列进行直接插入排序。然后缩小间隔 i ，重复上述操作，直至 i 缩小为1，此时所有的元素位于同一个序列且有序。由于刚开始时 i 较大， 每个子序列元素较少，排序速度较快。后期 i 变小，每个子序列元素较多，但大部分元素有序，所以排序速度仍然较快。一般 i 取 i/2。 希尔排序是一种不稳定的排序算法。实现如下
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
//时间复杂度：O(n) ~ O(n^2)
//空间复杂度：O(1)
//稳定性：不稳定
//内部排序
int n = (int)dataArr.count;
for (int gap = n / 2; gap > 0; gap /= 2){
for (int i = gap; i < n; i++){
for (int j = i - gap; j >= 0 && [dataArr[j] intValue] > [dataArr[j + gap] intValue]; j -= gap){
[dataArr exchangeObjectAtIndex:j withObjectAtIndex:(j + gap)];
}
}
}
NSLog(@"----%@", dataArr);
3、折半插入排序(二分法)
思想：当插入第 i (i >= 1)时，前面的V[0],...,V[i-1]等 i-1 个元素已经有序。这时，折半搜索第 i 个元素在前 i-1 个元素V[i-1],...V[0]中的插入位置，然后将V[i]插入，同时原来位置上的元素向后顺移。与直接插入排序不同的是，折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），但其减少了比较次数，所以该算法仍然比直接插入排序好。折半插入排序是一种稳定的排序算法。实现如下：
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
// 时间复杂度：O(N^2)
// 稳定性：稳定
// 内部排序
for (int i = 1; i < dataArr.count; i++) {
int left = 0;
int right = i - 1;
int mid;
int temp = [dataArr[i] intValue];
if (temp < [dataArr[right] intValue]) {
while (left <= right) {
mid = (left + right) / 2;
if ([dataArr[mid] intValue] < temp) {
left = mid + 1;
}else if ([dataArr[mid] intValue] > temp) {
right = mid - 1;
}else {
left += 1;
}
}
for (int j = i; j > left; j--) {
[dataArr exchangeObjectAtIndex:j-1 withObjectAtIndex:j];
}
dataArr[left] = [NSNumber numberWithInt:temp];
}
}
NSLog(@"折半插入排序----%@", dataArr);
4、直接选择排序
思想：第一次从 V[0]~V[n-1] 中选取最小值，与V[0]交换，第二次从 V[1]~V[n-1] 中选取最小值，与V[1]交换,...,第 i 次从 V[i-1]~V[n-1] 中选取最小值，与V[n-2]交换，总共通过 n-1 次，得到一个按从小到大的有序排列。实现如下：
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
// 时间复杂度：O(N^2)
// 空间复杂度：O(1)
// 稳定性：不稳定
// 内部排序
for (int i = 0; i < dataArr.count; i++) {
int mix = i;
for (int j = i + 1; j < dataArr.count; j++) {
if ([dataArr[mix] integerValue] > [dataArr[j] integerValue]) {
[dataArr exchangeObjectAtIndex:j withObjectAtIndex:mix];
}
}
}
NSLog(@"直接选择排序-----%@",dataArr);
5、堆排序
思想：堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。实现如下
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
/*
从最后一个非叶子节点开始 自下而上进行调整堆
*/
for (NSInteger i=(dataArr.count/2-1); i >= 0; --i) {
dataArr = [self maxHeapAdjust:dataArr index:i length:dataArr.count] ;
}
NSInteger num = dataArr.count;
/*
剩余的元素个数不为1时则继续调整，取出元素。取出的元素放在最后的一个节点。然后减小堆的元素的个数。所以大顶堆排序出来的是升序的。
*/
while (num > 1) {
[dataArr exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
dataArr=[self maxHeapAdjust:dataArr index:0 length:num-1];
num--;
}
NSLog(@"堆排序-----%@",dataArr);
- (NSMutableArray*)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index length:(NSInteger)length {
NSInteger leftChildIndex =index*2+1;//获取该节点的左子节点索引
NSInteger rightChildIndex=index*2+2;//获取该节点的右子节点索引
NSInteger maxValueIndex=index;//暂时把该索引当做最大值所对应的索引
// leftChildIndex < length
// 判断左子节点的值是否大于当前最大值
if (leftChildIndex < length && [array[leftChildIndex] integerValue] > [array[maxValueIndex] integerValue]) {
//把左子节点的索引作为最大值所对应的索引
maxValueIndex=leftChildIndex;
}
// rightChildIndex < length
// 判断左子节点的值是否大于当前最大值
if (rightChildIndex < length && [array[rightChildIndex] integerValue] > [array[maxValueIndex] integerValue]) {
maxValueIndex=rightChildIndex;
}
//如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
if (maxValueIndex != index) {
[array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
//递归乡下调整，此时maxValueIndex索引所对应的值是 刚才的父节点。
array=[self maxHeapAdjust:array index:maxValueIndex length:length];
}
return array;
}
6、冒泡排序
思想：根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。冒泡排序是一种稳定的排序算法，其实现如下
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
for (int i = 0; i < dataArr.count; ++i) {
//遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
for (int j = 0; j < dataArr.count-1; ++j) {
//根据索引的`相邻两位`进行`比较`
if ([dataArr[j] integerValue] > [dataArr[j+1] integerValue]) {
[dataArr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"冒泡排序%@",dataArr);
7、快速排序
思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排序算法。实现如下：
NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
[self quickSortArray:dataArr withLeftIndex:0 andRightIndex:dataArr.count-1];
NSLog(@"快速排序%@",dataArr);
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
8、归并排序
思想：其中，”归”是指将原序列分成半子序列，分别对子序列进行递归排序；”并”是指将排好序的各子序列合并成原序列。归并排序算法是一个典型的递归算法，因此也是概念上最为简单的排序算法。与快速排序算法相比，归并排序算法不依赖于初始序列，并且是一种稳定的排序算法，但需要与原序列一样大小的辅助存储空间。实现如下：
self.dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
NSMutableArray *tempArray = [NSMutableArray array];
//将数组中的每一个元素放入一个数组中
for (NSNumber *number in self.dataArr) {
NSMutableArray *childArray = [NSMutableArray array];
[childArray addObject:number];
[tempArray addObject:childArray];
}
//对这个数组中的数组进行合并，直到合并完毕为止
while (tempArray.count != 1) {
NSUInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArray:tempArray[i] secondArray:tempArray[i+1]];
[tempArray removeObjectAtIndex:i+1];
i += 1;
}
}
DLog(@"%@",tempArray);
// 归并排序中的“并”--合并：将两个有序数组进行合并
//
// - parameter firstList: 第一个有序数组
// - parameter secondList: 第二个有序数组
- (NSMutableArray *)mergeArray:(NSMutableArray *)firstArray secondArray:(NSMutableArray *)secondArray {
NSMutableArray *resultArray = [NSMutableArray array];
NSUInteger firstIndex = 0;
NSUInteger secondIndex = 0;
while (firstIndex < firstArray.count && secondIndex < secondArray.count) {
if ([firstArray[firstIndex] integerValue] < [secondArray[secondIndex] integerValue]) {
[resultArray addObject:firstArray[firstIndex]];
firstIndex += 1;
}else {
[resultArray addObject:secondArray[secondIndex]];
secondIndex += 1;
}
}
while (firstIndex < firstArray.count) {
[resultArray addObject:firstArray[firstIndex]];
firstIndex += 1;
}
while (secondIndex < secondArray.count) {
[resultArray addObject:secondArray[secondIndex]];
secondIndex += 1;
}
return resultArray;
}
9、分配排序(基数排序)
算法示意图：
下方的基数排序算法的实现是利用“桶”来实现的，首先我们创建10个桶，然后按照基数入桶，基数的取值是从数字的低位到高位以此取值。我们还是以[62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93]这个序列为例，使用基数排序的方式对该序列进行升序排列。
下方截图就是上述序列基数排序的具体过程，在排序之前我们先得创建10个空桶，并进行0-9的编号。这10个空桶会在基数排序的过程中存储我们要排序的数值。下方就是对基数排序步骤的详细介绍：
- 以无序序列数值的个数为基数，将无序序列中的值进入到基数对应的桶中。以51为例，如果取个位数为基数的话，51的基数就为1，那么51就进入如编号为1的桶中。以此类推，62在本轮入桶过程中就进入编号为2的桶中。以个位数为基数入桶的结果如下所示。
- 个位数为基数入桶完毕后，在安装编号从小到大将桶中的数据以此取出，在存入我们之前的数组中
- 在第二步生成的数组的基础上再以十位数为基数入桶。入桶完毕后，再次按照桶的编号顺序将数值取出。
- 因为在下方无序的数据中，最大值不超过两位，所以以十位为基数入桶出桶后就已经是有序的了。如果最大值是十万，那么我们一直取基数入桶到十万位为止。也就是排序的数值越大，我们入桶出桶的次数就越多，所以随着位数的增大，排序效率会下降。
