排序算法
2021-02-22 本文已影响0人
甲乙飞鱼
冒泡排序
- (void)sort {
for (NSInteger end = self.array.count - 1; end > 0; end--) {
//初始值等于1 防止数组未排序前就是有序数组 （第二个循环一次未修改 第一个循环直接退出）
NSInteger isNum = 1;
for (NSInteger i = 1; i <= end; i++) {
if ([self cmp:i-1 to:i] > 0) {
[self swapIndex:i to:i-1];
isNum = i;
}
}
end = isNum;
}
}
- 平均时间复杂度 O(n * n)
- 平均空间复杂度 O(0)
- 不稳定排序
选择排序
- (void)sort {
for (NSInteger end = self.array.count - 1; end > 0; end--) {
NSInteger isNum = 0;
for (NSInteger i = 1; i <= end; i++) {
if ([self cmp:i to:isNum] > 0) {
isNum = i;
}
}
[self swapIndex:isNum to:end];
}
}
- 每扫描一遍 记录最大值 与最后位置交换
- 平均时间复杂度 O(n * n)
- 平均空间复杂度 O(0)
- 不稳定排序
堆排序
- (void)sort {
self.heapSize = (int)self.array.count;
// 原地建堆 （最大堆）
for (int i = (self.heapSize >> 1) - 1; i >= 0; --i) {
//所有的非叶子节点依次下虑 最大堆就排好了
[self siftDown:i];
}
//交换堆顶元素和尾元素 （交换一次微元素位置 --1）
//尾元素位置 == 1 时数组有序了
while(self.heapSize > 1) {
[self swapIndex:0 to:--self.heapSize];
[self siftDown:0];
}
}
- 下虑代码
- (void)siftDown:(int)index {
int element = [self.array[index] intValue];
int childIndex;
//self.heapSize >> 1 最后一个非叶子节点的 index
//index 每次传入的是最后一个飞叶子节点-1
//half 最后一个非叶子节点的 index
//index < half ; index = childIndex
//这个index < half
//因为 index = childIndex childIndex 必然大于 index
//第一次循环index = half 然后每次循环都是 index > half 所以在等待循环里的break; break 时 下虑到了叶子节点
for(int half = self.heapSize >> 1; index < half; index = childIndex) {
//左子节点的 index
childIndex = (index << 1) + 1;
//左子节点的 index位置的值
int child = [self.array[childIndex] intValue];
//右子节点的 index
int rightIndex = childIndex + 1;
//rightIndex < self.heapSize 节点的index 必须小于数组的size
//[self cmpElement:[self.array[rightIndex] intValue] to:child]
//右子节点的值 大于 左子节点的值
if (rightIndex < self.heapSize && [self cmpElement:[self.array[rightIndex] intValue] to:child] > 0) {
// 记录 左右子节点 比较大的值 和 index
childIndex = rightIndex;
child = [self.array[rightIndex] intValue];
}//这里没有else 是因为 childIndex child 已经记录了 左子节点的index 和 值了
// 如果 父节点的值 大于 最大子子节点的值 则不需下虑 退出此次循环
if ([self cmpElement:element to:child] >= 0) {
break;
}
//如果 父节点的值 小于于 最大子子节点的值 则需下虑 继续循环下去
self.array[index] = @(child);
}
self.array[index] = @(element);
}
- 排序思路代码里注释的写的还是比较全的
- 平均时间复杂度 O(n log n)
- 平均空间复杂度 O(0)
- 不稳定排序
插入排序
- (void)sort {
for (int begin = 1; begin < self.array.count; begin++) {
// 待插入元素的索引
int a = begin;
// 待插入元素
int b = [self.array[a] intValue];
// 判断插入位置 并把插入位置到待插入位置的元素往后挪移一位
while (a > 0 && [self cmpElement:b to:[self.array[a - 1] intValue]] < 0) {
self.array[a] = self.array[a-1];
a--;
}
// 待插入元素放到最终的何时位置
self.array[a] = @(b);
}
}
- 扫描一遍 每扫到一个值 就开始找这个值在前面那个位置插入
- 平均时间复杂度 O(n * n) 可优化查找插入位置用二分法
- 平均空间复杂度 O(0)
- 不稳定排序
归并排序
- (void)sort {
self.leftArr = [NSMutableArray array];
[self sortBegin:0 end:self.array.count];
}
- (void)sortBegin:(NSInteger)begin end:(NSInteger)end {
if (end - begin >= 2) {
NSInteger mid = (begin + end) >> 1;
// 不断地将当前序列平均分割成2个子序列
// 知道不能再分割（序列里只剩一个元素）
[self sortBegin:begin end:mid];
[self sortBegin:mid end:end];
// 不断地将两个子序列合并成一个有序的序列
// 最终只剩一个有序序列
[self mergeBegin:begin mid:mid end:end];
}
}
- (void)mergeBegin:(NSInteger)begin mid:(NSInteger)mid end:(NSInteger)end {
NSInteger li = 0; //归并的两个数组的第一个数组的左边 index
NSInteger le = mid - begin; //归并的两个数组的第一个数组的右边 index
NSInteger ri = mid; //归并的两个数组的第二个数组的左边 index
NSInteger re = end; //归并的两个数组的第二个数组的右边 index
NSInteger ai = begin; //归并的两个数组覆盖到那个位置了
//备份左边数组的元素
for(NSInteger i = li; i < le; ++i) {
self.leftArr[i] = self.array[begin + i];
}
while(true) {
while(li < le) {
if (ri < re && [self cmpElement:[self.array[ri] intValue] to:[self.leftArr[li] intValue]] < 0) {
self.array[ai++] = self.array[ri++];
} else {
self.array[ai++] = self.leftArr[li++];
}
}
return;
}
}
不断地将当前序列平均分割成2个子序列
直到不能再分割（序列里只剩一个元素）
不断地将两个子序列合并成一个有序的序列
最终只剩一个有序序列
- 平均时间复杂度 O(n log n)
- 平均空间复杂度 O(n)
- 稳定排序
快速排序
- (void)sort {
[self sortBegin:0 end:self.array.count];
}
//对 [begin, end) 范围的元素进行快速排序
- (void)sortBegin:(NSInteger)begin end:(NSInteger)end {
if (end - begin < 2) return;
// 确定轴点位置 O(n)
NSInteger mid = [self pivotIndexBegin:begin end:end];
// 对子序列进行快速排序
[self sortBegin:begin end:mid];
[self sortBegin:mid+1 end:end];
}
/// 构造出 [begin, end) 范围的轴点元素 返回轴点元素的最终位置
- (NSInteger)pivotIndexBegin:(NSInteger)begin end:(NSInteger)end {
NSInteger a = begin + (NSInteger)(arc4random() % (end - begin));
// 随机选择一个元素跟begin位置进行交换
[self swapIndex:begin to:a];
// 备份begin位置的元素
int pivot = [self.array[begin] intValue];
// end指向最后一个元素
end--;
while (begin < end) {
while (begin < end) {
if ([self cmpElement:pivot to:[self.array[end] intValue]] < 0) { // 右边元素 > 轴点元素
end--;
} else { // 右边元素 <= 轴点元素
self.array[begin++] = self.array[end];
break;
}
}
while (begin < end) {
if ([self cmpElement:pivot to:[self.array[begin] intValue]] > 0) { // 左边元素 < 轴点元素
begin++;
} else { // 左边元素 >= 轴点元素
self.array[end--] = self.array[begin];
break;
}
}
}
// 将轴点元素放入最终的位置
self.array[begin] = @(pivot);
// 返回轴点元素的位置
return begin;
}
- 快速排序的本质：逐渐将每一个元素转化为轴点元素
- 平均时间复杂度 O(n log n)
- 平均空间复杂度 O(logn)
- 不稳定排序
希尔排序
- (void)sort {
NSMutableArray *stepSequence = [self sedgewickStepSequence];
for (NSInteger i = 0; i < stepSequence.count; i++) {
int step = [stepSequence[i] intValue];
[self sort1:step];
}
}
//根据步长序列排序 根据分成step列 进行排序
- (void)sort1:(int)step {
//col:第几列 column的简称
for (int col = 0; col < step; col++) {
for (int begin = step + col; begin < self.array.count; begin += step) {
int cur = begin;
while (cur > col && ([self cmp:cur to:cur - step] < 0)) {
[self swapIndex:cur to:cur-step];
cur -= step;
}
}
}
}
- 根据元素的个数获取步长序列，根据步长序列分成不同的列数 分别对每一列进行排序 知道步长序列为1 此时数组有序
- 平均时间复杂度 O(n log n)
- 平均空间复杂度 O(logn)
- 不稳定排序
