iOS算法
2018-04-18 本文已影响0人
Junetaurus
排序方法
- 选择排序：直接选择排序、堆排序。
- 交换排序：冒泡排序、快速排序。
- 插入排序：直接插入排序、二分法插入排序、希尔排序。
- 归并排序
- 基数排序
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏) | 时间复杂度（最好) | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 直接选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | 较复杂 |
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(nlog2n) | 不稳定 | 较复杂 |
| 直接插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 希尔排序 | O(nlog2n) | O(n2) | O(n) | O(1) | 不稳定 | 较复杂 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | 较复杂 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 较复杂 |
- 注：基数排序中r代表关键字的基数，d 代表长度，n 代表关键字的个数
选择排序
直接选择排序
- 对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量 k 来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
- (void)selectionSortWithArray:(NSMutableArray *)array {
for (NSInteger i = 0; i < array.count; i ++) {
for (NSInteger j = i + 1; j < array.count; j ++) {
if (array[i] < array[j]) {
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
堆排序
- 先将初始文件 R[1..n] 建成一个大根堆，此堆为初始的无序区
- 再将关键字最大的记录 R[1]（即堆顶）和无序区的最后一个记录 R[n] 交换，由此得到新的无序区 R[1..n-1] 和有序区 R[n]，且满足 R[1..n-1].keys≤R[n].key
- 由于交换后新的根 R[1] 可能违反堆性质，故应将当前无序区 R[1..n-1] 调整为堆。然后再次将 R[1..n-1] 中关键字最大的记录 R[1] 和该区间的最后一个记录 R[n-1] 交换，由此得到新的无序区 R[1..n-2] 和有序区 R[n-1..n]，且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys，同样要将 R[1..n-2] 调整为堆。
- 直到无序区只有一个元素为止。
- (void)heapSort:(NSMutableArray *)array {
NSInteger i , size;
size = array.count/1.0;
// 从子树开始整理树
for (i = array.count/1.0 - 1; i >= 0; i--) {
[self createBiggestHeap:array withSize:size beIndex:i];
}
//拆除树
while (size > 0) {
[array exchangeObjectAtIndex:size - 1 withObjectAtIndex:0];//将根（最小）与数组最末交换
size--;//树大小减小
[self createBiggestHeap:array withSize:size beIndex:0];//整理树
}
}
- (void)createBiggestHeap:(NSMutableArray *)array withSize:(NSInteger)size beIndex:(NSInteger)element {
NSInteger lchild = element * 2 + 1, rchild = lchild + 1;//左右子树
while (rchild < size) {//子树均在范围内
//如果比左右子树都小，完成整理
if (array[element] <= array[lchild] && array[element] <= array[rchild]) return;
//如果左边最小
if(array[lchild] <= array[rchild]){
[array exchangeObjectAtIndex:element withObjectAtIndex:lchild];//把左面的提到上面
element = lchild;//循环时整理子树
}else{
//否则右面最小
[array exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 + 1;
rchild = lchild + 1;//重新计算子树位置
}
//只有左子树且子树小于自己
if (lchild < size && array[lchild] < array[element]) {
[array exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
交换排序
冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- (void)bubbleSortWithArray:(NSMutableArray *)array {
for (int i = 0; i < array.count; i++) {
for (int j = 0; j < array.count - i - 1; j++) {
if (array[j] < array[j+1]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
}
快速排序
- 设置两个变量 i、j，排序开始的时候：i = 0，j = N-1；
- 以第一个数组元素作为关键数据，赋值给 key，即 key = A[0]；
- 从 j 开始向前搜索，即由后开始向前搜索 （j--），找到第一个小于 key 的值 A[j]，将 A[j] 和 A[i] 互换；
- 从 i 开始向后搜索，即由前开始向后搜索 （i++），找到第一个大于 key 的 A[i]，将 A[i] 和 A[j] 互换；
- 重复第3、4步，直到 i = j； (3，4 步中，没找到符合条件的值，即 3 中 A[j] 不小于 key，4 中 A[i] 不大于 key 的时候改变 j、i 的值，使得 j = j - 1，i = i + 1，直至找到为止。找到符合条件的值，进行交换的时候 i， j 指针位置不变。另外，i == j 这一过程一定正好是 i++ 或 j-- 完成的时候，此时令循环结束）。
- (void)quickSortWithArray:(NSMutableArray *)array withLeft:(NSInteger)left andRight:(NSInteger)right {
if (left >= right) return; /*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
NSInteger i = left;
NSInteger j = right;
NSInteger key = [array[left] integerValue];
while (i < j) { /*控制在当组内寻找一遍*/
while (i < j && key <= [array[j] integerValue]) {
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
j--;/*向前寻找*/
}
array[i] = array[j]; /*找到一个这样的数后就把它赋给前面的被拿走的i的值*/
while (i < j && key >= [array[i] integerValue]) {
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
i++;/*向后寻找*/
}
array[j] = array[i];
}
array[i] = [NSNumber numberWithInteger:key];
[self quickSortWithArray:array withLeft:left andRight:i - 1];
[self quickSortWithArray:array withLeft:i + 1 andRight:right];
}
插入排序
直接插入排序
- 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
- (void)insertSort:(NSMutableArray *)array {
for (NSInteger i = 1; i < array.count; i++) {
NSInteger j = i;
NSInteger temp = [array[i] integerValue];
while (j > 0 && temp < [array[j - 1] integerValue]) {
[array replaceObjectAtIndex:j withObject:array[j - 1]];
j--;
}
[array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
}
折半插入排序（二分插入排序）
- 计算 0 ~ i - 1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
- 在相应的半个范围里面找插入的位置时，不断的用上述步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；
- 确定位置之后，将整个序列后移，并将元素插入到相应位置。
- (void)binaryInsertSort:(NSMutableArray *)array {
for (NSInteger i = 1; i < array.count; i++) {
NSInteger temp = [array[i] integerValue];
NSInteger left = 0;
NSInteger right = i - 1;
while (left <= right) {
NSInteger middle = (left + right) / 2;
if (temp < [array[middle] integerValue]) {
right = middle - 1;
}else{
left = middle + 1;
}
}
for (NSInteger j = i; j > left; j--) {
[array replaceObjectAtIndex:j withObject:array[j - 1]];
}
[array replaceObjectAtIndex:left withObject:[NSNumber numberWithInteger:temp]];
}
}
希尔排序（缩小增量排序）
- 先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达等于 1时，所有记录在统一组内排好序。
+ (void)shellSort:(NSMutableArray *)array {
NSInteger gap = array.count / 2;
while (gap >= 1) {
for (NSInteger i = gap ; i < array.count; i++) {
NSInteger temp = [array[i] integerValue];
NSInteger j = i;
while (j >= gap && temp < [array[j - gap] integerValue]) {
[array replaceObjectAtIndex:j withObject:array[j - gap]];
j -= gap;
}
[array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
}
归并排序
- 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
- 在归并的过程中计算每个小区间的逆序对数，进而计算出大区间的逆序对数
- (NSMutableArray *)mergeSort:(NSMutableArray *)array withCapacity:(NSInteger)n {
NSMutableArray *p = [NSMutableArray arrayWithCapacity:n];
[self mergeSort:array withFirst:0 withLast:n-1 ResultAry:p];
return p;
}
- (void)mergeSort:(NSMutableArray *)array withFirst:(NSInteger)first withLast:(NSInteger)last ResultAry:(NSMutableArray *)temp{
if (first < last) {
NSInteger mid = (first + last) / 2;
// 左边有序
[self mergeSort:array withFirst:first withLast:mid ResultAry:temp];
// 右边有序
[self mergeSort:array withFirst:mid + 1 withLast:last ResultAry:temp];
// 将二个有序数列合并
[self mergearray:array withFirst:first withMid:mid withLast:last ResultAry:temp];
}
}
- (void)mergearray:(NSMutableArray *)array withFirst:(NSInteger)first withMid:(NSInteger)mid withLast:(NSInteger)last ResultAry:(NSMutableArray *)temp{
NSInteger i = first, j = mid + 1;
NSInteger m = mid ,n = last;
NSInteger k = 0;
while (i <= m && j <= n) {
if (array[i] <= array[j]) temp[k++] = array[i++];
else temp[k++] = array[j++];
}
while (i <= m) temp[k++] = array[i++];
while (j <= n) temp[k++] = array[j++];
for (i = 0; i < k; i++) array[first + i] = temp[i];
}
基数排序
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
- 基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
- (void)radixAscendingOrderSort:(NSMutableArray *)array {
//创建空桶
NSMutableArray *buckt = [self createBucket];
//待排数组的最大数值
NSNumber *maxnumber = [self listMaxItem:array];
//最大数值的数字位数
NSInteger maxLength = [self numberLength:maxnumber];
// 按照从低位到高位的顺序执行排序过程
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in array) {
//确定item 归属哪个桶 以digit位数为基数
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
//将数据放入空桶上
[mutArray addObject:item];
}
NSInteger index = 0;
//出桶
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
//将桶的数据放回待排数组中
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
array[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
}
//创建空桶
- (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
//数据最大值
- (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
//数字的位数
- (NSInteger)numberLength:(NSNumber *)number {
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
//digit为基数位数
if (digit > 0 && digit <= [self numberLength:number]) {
NSMutableArray *numbersArray = [NSMutableArray array];
// number的位数确定
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
for (int index = 0; index < [self numberLength:number]; index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
// number的位数 是几位数的
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
