目录:
- 冒泡排序
- 快速排序
- 选择排序
- 插入排序
- 归并排序
冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
冒泡算法是一种基础的排序算法, 这种算法会重复的比较数组中相邻的两个元素. 如果一个元素比另一个元素大（小）, 那么就交换这两个元素的位置. 重复这一比较直至最后一个元素. 这一比较会重复n-1趟, 每一趟比较n-j次, j 是已经排序好的元素个数. 每一趟比较都能找出未排序元素中最大或者最小的那个数字. 这就如同水泡从水底逐个飘到水面一样. 冒泡排序是一种时间复杂度较高, 效率较低的排序方法.
- 实现描述
1，每一趟比较都比较数组中两个相邻元素的大小
2，如果i元素小于i-1元素，就调换两个元素的位置
3，重复n-1趟的比较
冒泡排序
- 代码实现:
#pragma mark - 冒泡排序
- (void)bubbleSort {
NSMutableArray *dataArray = [@[@5,@1,@8,@4,@6,@2,@7,@3,@0,@9] mutableCopy];
for (int i = 0; i < dataArray.count-1; i++) {
for (int j = 0; j < dataArray.count-1-i; j++) {
if ([dataArray[j+1] intValue] > [dataArray[j] intValue]) {
int tmp = [dataArray[j] intValue];
dataArray[j] = dataArray[j+1];
dataArray[j+1] = [NSNumber numberWithInt:tmp];
}
}
}
NSLog(@"bubbleSort: %@",dataArray);
}
快速排序
快速排序是当遇到较大数据时,排序快,高效的方法.
- 算法描述：
1．先从数列中取出一个数作为基准数.
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边.
3．再对左右区间重复第二步，直到各区间只有一个数.
快速排序
代码实现:
#pragma mark - 快速排序算法
//给快速排序方法连个参数,开始位置(左),和结束位置(右)
- (void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right {
//开始位置坐标小于结束位置坐标时,
if (left < right) {
//temp中存的就是基准数(基准数是随机的,但一般都是第一个元素)
NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
//递归调用
//继续处理左边的，这里是一个递归的过程
[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp - 1];
//继续处理右边的 ，这里是一个递归的过程
[self quickAscendingOrderSort:arr leftIndex:temp + 1 rightIndex:right];
}
NSLog(@"快速升序排序结果：%@", arr);
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right {
NSInteger tempValue = [arr[left] integerValue];
while (left < right) {
//顺序很重要，要先从右边开始找
while (left < right && tempValue <= [arr[right] integerValue]) {
right --;
}
if (left < right) { //再找左边的
arr[left] = arr[right];
}
while (left < right && [arr[left] integerValue] <= tempValue) {
left ++;
}
if (left < right) { //交换两个数在数组中的位置
arr[right] = arr[left];
}
}
//此时left = right,最终将基准数归位
arr[left] = [NSNumber numberWithInteger:tempValue];
return left;
}
选择排序：
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 算法描述：
- 设数组内存放了n个待排数字，数组下标从1开始，到n结束.
- I=1
- 从数组的第i个元素开始到第n个元素，寻找最小的元素.（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）
- 将上一步找到的最小元素和第i位元素交换.
如果i=n－1算法结束，否则回到第3步.
选择排序
- 代码实现:
#pragma mark - 选择排序
- (void)selectionSort {
NSMutableArray *dataArray = [@[@5,@1,@8,@4,@6,@2,@7,@3,@0,@9] mutableCopy];
for (int i = 0; i < dataArray.count; i++) {
for (int j = i +1; j < dataArray.count; j++) {
if ([dataArray[i] intValue] > [dataArray[j] intValue]) {
int tmp = [dataArray[i] intValue];
dataArray[i] = dataArray[j];
dataArray[j] = [NSNumber numberWithInt:tmp];
}
}
}
NSLog(@"selectionSort: %@",dataArray);
}
插入排序
插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 算法描述:
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
4, 将新元素插入到该位置后；重复步骤2~5。
插入排序
- 代码实现:
#pragma mark - 插入排序
- (void)insertSort {
NSMutableArray *dataArray = [@[@5,@1,@8,@4,@6,@2,@7,@3,@0,@9] mutableCopy];
for (int i = 1; i < dataArray.count; i++) {
int tmp = [dataArray[i] intValue];
for (int j = i-1; j >= 0 && tmp < [dataArray[j] intValue]; j--) {
dataArray[j+1] = dataArray[j];
dataArray[j] = [NSNumber numberWithInt:tmp];
}
}
NSLog(@"插入: %@",dataArray);
}
归并排序
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列.
并归排序
- 代码实现
#pragma mark - 归并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
while (tempArray.count != 1) {
NSInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
i++;
}
}
NSLog(@"归并升序排序结果：%@", ascendingArr);
}
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
NSMutableArray *resultArray = [NSMutableArray array];
NSInteger firstIndex = 0, secondIndex = 0;
while (firstIndex < array1.count && secondIndex < array2.count) {
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
return resultArray.copy;
}
网友评论