记录一下常用的算法， 方便以后复习或者查阅， 有的还需要优化
1.冒泡算法
主要思路就是从数组的最后面的元素开始比较，前面一个元素比后面一个元素要大的话， 就交换位置。 采用一个Falg标志位是为了优化算法， 因为有可能冒泡交换一定次数的时候数组就已经是按顺序排序了， 所以就可以停止循环了
时间复杂度最好是O(n), 最差是O(n * n)
-(void)BubbleSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
BOOL flag = YES;
// NSNumber *temp = nil;
int count = (int)array.count;// NSUInteger 转化为 int ，要不有问题
for (int i = 0; i < count && flag; i++) {
flag = NO;
for (int j = (count - 2); j >= i; j--) {
NSLog(@"%zd--%zd\n", i, j);
if (array[j] > array[j + 1]) {
// temp = array[j];
// array[j] = array[j + 1];
// array[j + 1] = temp;
[array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
flag = YES;//来到这里证明还是要交换的，直到不进这里说明已经排好序了， 后面就不用继续遍历比较了
NSLog(@"%@", array);
}
}
}
}
2.选择排序
主要思路就是：把当前元素当做最小的元素，跟数组里面自己位置后面的每一个元素比较，如果比自己小，则记录最小元素的下标， 比较完毕后， 当前元素元素和最小元素的位置交换。
时间复杂度是O(n * n)，性能比冒泡算法要好
-(void)simpleSelectionSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
int count = (int)array.count;// NSUInteger 转化为 int ，要不有问题
int min;
for (int i = 0 ; i < count; i++) {
min = i;
for (int j = i + 1; j < count; j++) {
if (array[min] > array[j]) {
min = j;
}
}
if (min != i) {
// NSNumber *temp = array[min];
// array[min] = array[i];
// array[i] = temp;
[array exchangeObjectAtIndex:min withObjectAtIndex:i];
}
}
NSLog(@"%@", array);
}
3.直接插入算法
直接插入算法：将一个记录插入到已经排好序的有序表中， 从而得到一个新的， 记录数增1 的有序表；
本例中： 2， 4， 5， 中已经排好序了， 接下来的 1 要插入到第一个位置，先记录1所在位置的数值1， 然后 5，4，2，按顺序往后挪动一个位置， 1 的位置 变成5， 5的位置变成4， 4 的位置变成2， 然后再把之前记录1所在位置的数值1赋值到没挪动2之前的位置， 变成了 1（2），2（4），4（5），5（1），括号为挪动前的位置。
时间复杂度为O(n * n); 性能比选择排序要好。
//直接插入算法
-(void)straightInsertionSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
int count = (int)array.count;// NSUInteger 转化为 int ，要不有问题
NSNumber *temp = nil;
int i, j;
for (i = 1; i < count; i++) {//从第二个元素开始
temp = array[i];
for (j = i; j > 0 && array[j-1]>temp; j--) {
array[j] = array[j-1];
}
array[j] = temp;
}
NSLog(@"%@", array);
}
4.希尔算法
希尔排序为不稳定性排序。因为相同的元素可能在各自的插入排序中移动，所以它的稳定性就被打破了。可能有人想问，稳定性是干嘛的啊？稳定的意思是指相同的元素在排序后的相对位置不变。比如有两个5 ，作为区分前面的叫5(1)，后面的叫5(2)，排序完成后5(1)还在5(2)的前面。那你可能会问，反正是一样的，换了就换呗。但是在实际应用中被排序的对象会拥有不同的属性，举个栗子，公司在招聘时，想要年龄小的，所以对所有人进行了按年龄的排序。之后还想看成绩分数高的。所以在按成绩进行排序时就有可能出现成绩一样的，但他们的年龄不一样，而你不能把成绩相同但年龄大的排在小的前面。此时算法的稳定性就有了意义。
时间复杂度为O(n^(3/2); 性能比插入排序要好， 不稳定排序。
#pragma mark - 希尔算法
-(void)shellSort {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@2,@4,@5,@1,@9,@7,@6,@8,@3, nil];
int count = (int)array.count;
//初始增量为数组长度的一半，然后每次除以2取整
for (int increment = count/2; increment>0; increment /=2) {
//初始下标设为第一个增量的位置，然后递增
for (int i = increment; i<count; i++) {
//获取当前位置
int j = i;
//然后将此位置之前的元素，按照增量进行跳跃式比较
while (j-increment>=0 && array[j]<array[j-increment]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
j-=increment;
}
}
}
NSLog(@"%@", array);
}
5.堆排序算法
时间复杂度为O(nlogn); 不稳定排序
/堆排序算法
-(void)HeapSort {
/*
测试数据
*/
NSArray *array=@[@3,@2,@6,@4,@1,@0,@6,@7,@5];
NSMutableArray *mutable=[NSMutableArray arrayWithArray:array];
mutable=[self createMaxHeap:mutable];
//NSInteger num=mutable.count;
/*
剩余的元素个数不为1时则继续调整，取出元素。取出的元素放在最后的一个节点。然后减小堆的元素的个数。所以大顶堆排序出来的是升序的。
*/
for (NSInteger num=mutable.count; num > 1; num--){
[mutable exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
mutable=[self maxHeapAdjust:mutable index:0 length:num-1];
}
NSLog(@"%@", mutable);
//主要思路：
//1.如何构建由一个无序序列建成的一个堆
//2.如何在输出堆顶元素后，调整剩余元素成为一个新的堆
}
-(NSMutableArray*)createMaxHeap:(NSMutableArray*)array
{
/*
从最后一个非叶子节点开始 自下而上进行调整堆
*/
for (NSInteger i=(array.count/2-1);i>=0; --i)
{
array=[self maxHeapAdjust:array index:i length:array.count] ;
}
return array;
}
/*
调整堆 递归调整的过程。这个调整堆的方法传入的是待调整的数组，数组元素的长度（为什么不直接用array.count呢？因为再进行排序
的时候，我们会动态更改无序堆的长度，而array的长度确是不变的，所以不用array.cout） 其实每调用一次调整堆方法，我们相当于只调整3个元素：父节点，左、右子节点。当左子结点是三者中最大的时候，把它和父节点进行交换。然后再递归调整以刚才的父节点（现在被降级为左子节点）为父节点的三个节点。此时为什么不用调整右子节点呢？这是由于我们建立大顶堆的过程中，都是自下而上进行调整的，此时我们没有动右子节点，且右子节点和现在的父节点（原来的左子节点）满足大顶堆的条件，所以不用调整。
*/
-(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你
//array[leftChildIndex]>array[maxValueIndex] 判断左子节点的值是否大于当前最大值
if (leftChildIndex<length && array[leftChildIndex]>array[maxValueIndex])
{
//把左子节点的索引作为最大值所对应的索引
maxValueIndex=leftChildIndex;
}
// rightChildIndex<length
//array[leftChildIndex]>array[maxValueIndex] 判断左子节点的值是否大于当前最大值
if (rightChildIndex<length && array[rightChildIndex]>array[maxValueIndex])
{
maxValueIndex=rightChildIndex;
}
//如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
if (maxValueIndex!=index)
{
[array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
//递归乡下调整，此时maxValueIndex索引所对应的值是 刚才的父节点。
array=[self maxHeapAdjust:array index:maxValueIndex length:length];
}
return array;
}
6.归并排序
时间复杂度为O(nlogn); 稳定排序
#pragma mark - 归并排序
-(void)mergeSort {
NSArray *array=@[@3,@2,@6,@4,@1,@0,@6,@7,@5];
//[self mergeSortWithArray:array];
[self mergeSortWithArray:[NSMutableArray arrayWithArray:array] WithStarIndex:0 WithEndIndex:array.count -1];
//稳定排序， 时间复杂度为O(nlogn)
}
-(void) mergeSortWithArray: (NSMutableArray *)array
WithStarIndex: (NSInteger) starIndex
WithEndIndex: (NSInteger) endIndex
{
//递归结束条件
if (starIndex >= endIndex) {
return;
}
//找出中点进行分解
NSInteger midIndex = (starIndex + endIndex)/2;
//递归分解前半部分
[self mergeSortWithArray:array WithStarIndex:starIndex WithEndIndex:midIndex];
//递归分解后半部分
[self mergeSortWithArray:array WithStarIndex:midIndex + 1 WithEndIndex:endIndex];
//经过上面的递归分解后，最小的子数组里只有一个元素，也就是有序的了，然后从底层进行递归合并
[self mergeWithArray:array WithStarIndex:starIndex WithMidIndex:midIndex WithEndIndex:endIndex];
}
//一次归并
-(void) mergeWithArray: (NSMutableArray *)array
WithStarIndex: (NSInteger) starIndex
WithMidIndex: (NSInteger) midIndex
WithEndIndex: (NSInteger) endIndex
{
//记录归并次数
static int sort_count = 0;
if (endIndex < starIndex) {
return;
}
//前半部分元素个数
NSInteger frontCount = midIndex - starIndex + 1;
//后半部分元素的个数
NSInteger rearCount = endIndex - midIndex;
//把数组拆分成两部分进行归并
//取出前半部分
NSMutableArray *frontArray = [[NSMutableArray alloc] initWithCapacity:frontCount];
for (NSInteger i = 0; i < frontCount; i ++) {
[frontArray addObject:array[starIndex + i]];
}
//取出后半部分
NSMutableArray *rearArray = [[NSMutableArray alloc] initWithCapacity:rearCount];
for (NSInteger i = 0; i < rearCount; i ++) {
[rearArray addObject:array[midIndex + i + 1]];
}
//进行比较归并
NSInteger fi = 0;
NSInteger ri = 0;
NSInteger oi = starIndex;
//当两个子数组中都有元素时才进行合并
while (fi < frontArray.count && ri < rearArray.count) {
if(frontArray[fi] <= rearArray[ri]){
array[oi++] = frontArray[fi++];
continue;
}
array[oi++] = rearArray[ri++];
}
//前面元素中经过合并后仍然有元素，把剩余的元素进行添加
while (fi < frontArray.count) {
array[oi++] = frontArray[fi++];
}
//后边元素经过合并后仍然有元素，把剩余元素进行添加
while (ri < rearArray.count) {
array[oi++] = rearArray[ri++];
}
NSLog(@"第%d合并结果如下：", ++ sort_count);
NSLog(@"%@", array);//最后一次拿到结果
}
7.快速排序
时间复杂度为O(nlogn), 不稳定排序,
-(void)quickSort {
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
NSLog(@"%@",arr);
//不稳定排序, 时间复杂度为O(nlogn)
}
- (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];
}
各种排序的关系
排序算法关系图
最后放上性能的比较图
各种排序算法的事件复杂度和稳定性
