iOS 常用算法
1.冒泡排序
冒泡算法是一种基础的排序算法，这种算法会重复的比较数组中相邻的两个元素，如果一个元素比另一个元素大/小，那么就交换这两个元素的位置。重复一直比较到最后一个元素.
1.最差时间复杂度：O(n^2);
2.平均时间复杂度：O(n^2);
/*冒泡排序*/
- (void)bubbleSortWithArray:(NSMutableArray *)array{
for (int i = 0; i < array.count; i++) {
for (int j = 0; j<array.count-1-i; j++) {
if ([array[j]integerValue] > [array[j+1] integerValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
}
2.选择排序
1.最差时间复杂度：O(n^2);
2.平均时间复杂度：O(n^2);
- (void)selectionSortWithWithArray:(NSMutableArray *)array{
for (int i = 0; i < array.count; i++) {
for (int j = i+1; j<array.count; j++) {
if ([array[i]integerValue] > [array[j] integerValue]) {
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
3.快速排序
image
设要排序的数组是mutableArray对象，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一次快速排序。
1 .设置两个变量i，j ，排序开始时i = 0，就j = mutableArray.count - 1；
2 .设置数组的第一个值为比较基准数key，key = mutableArray.count[0]；
3.因为设置key为数组的第一个值，所以先从数组最右边开始往前查找比key小的值。如果没有找到，j--继续往前搜索；如果找到则将mutableArray[i]和mutableArray[j]互换，并且停止往前搜索，进入第4步；
4.从i位置开始往后搜索比可以大的值，如果没有找到，i++继续往后搜索；如果找到则将mutableArray[i]和mutableArray[j]互换，并且停止往后搜索；
5 .重复第3、4步，直到i == j（此时刚好执行完第三步或第四部），停止排序；
/*快排**/
- (void)fastSortWithWithArray:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex{
if (leftIndex>= rightIndex) {
/*如果数组长度我0,或1时 返回*/
return;
}
/*去第一个下标为基数**/
NSInteger flag =leftIndex;
//取基准数
NSInteger num = [array[flag] integerValue];
while (flag <rightIndex) {
/*从右边开始取出比基数小的值*/
while (flag < rightIndex && [array[rightIndex] integerValue] >= num) {
rightIndex--;
}
/*如果比基数小，查找到小值到最最左边位置*/
array[flag] = array[rightIndex];
/*从左边开始取出比基数大的值*/
while (flag < rightIndex && [array[flag] integerValue] <= num) {
flag++;
}
/*如果比基数大，则查找到最大值为最右边位置**/
array[rightIndex] = array[flag];
}
array[flag] = @(num);
[self fastSortWithWithArray:array leftIndex:leftIndex rightIndex:flag-1];
[self fastSortWithWithArray:array leftIndex:flag+1 rightIndex:rightIndex];
}
4.插入排序
直接插入排序的基本思想是从第二个元素开始，依次和前面的元素比较，如果比前面的元素小则将元素依次向后移位，给需要插入的元素腾出空间。与选择排序类似的是当前索引左边的所有元素都是有序的，但是它们最终的位置不确定，因为后面可能还会出现更小或更大的元素。所以为了给更小或更大的元素腾出空间，它们随时都可能被移动。如果到达了数组的右端时，数组顺序就完成了。
/*插入排序**/
- (void)insertSortWithArray:(NSMutableArray *)array{
/*从第二个值开始*/
for (int i = 1; i < array.count; i++) {
/*记录下标*/
int j = i;
/*获取当前的值*/
NSInteger temp = [array[i] integerValue];
while (j > 0 &&temp < [array[j-1]integerValue]) {
/*把大于temp的值放到temp位置*/
[array replaceObjectAtIndex:j withObject:array[j-1]];
j--;
}
//然后把temp的值放在前面的位置
[array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
}
5.堆排序
堆排序(Heap Sort) 就是利用堆(假设利用大堆顶)进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
参考文章
/*堆排序*/
- (void)heapSortWithArray:(NSMutableArray *)array{
NSInteger i, size;
size = array.count;
for (i = array.count/2-1; i>=0; i--) {
[self creatBigHeapWithArray:array size:size beIndex:i];
}
while (size>0) {
[array exchangeObjectAtIndex:size-1 withObjectAtIndex:0];
size--;
[self creatBigHeapWithArray:array size:size beIndex:0];
}
NSLog(@"堆排序%@",array);
}
/*生成一个堆**/
- (void)creatBigHeapWithArray:(NSMutableArray *)array size:(NSInteger) size beIndex:(NSInteger)element{
/*左子树*/
NSInteger leftChild = element*2+1;
/*右子树*/
NSInteger rightChild = leftChild+1;
while (rightChild<size) {
if (array[element]>= array[leftChild] &&array[element]>= array[rightChild]) {
/*如果左右子树都大,完成整理*/
return;
}
if (array[leftChild]> array[rightChild]) {
/*如果左边的最大**/
/*把左边的提到上面*/
[array exchangeObjectAtIndex:element withObjectAtIndex:leftChild];
element = leftChild;
}else{
[array exchangeObjectAtIndex:element withObjectAtIndex:rightChild];
element = rightChild;
}
//重新计算子树位置
leftChild = element*2+1;
rightChild = leftChild+1;
}
//只有左子树且子树大于自己
if (leftChild<size &&array[leftChild]>array[element]) {
[array exchangeObjectAtIndex:leftChild withObjectAtIndex:element];
}
}
