https://www.cnblogs.com/angelye/p/7508292.html
OC 排序：
- 系统方法排序
- 快速排序
- 冒泡排序
- 选择排序
- 插入排序
#pragma mark - sort from min to max 从小到大排序
/**
* 比较排序 Comparator -- 系统方法
**/
- (void)comparatorSortWithArray:(NSMutableArray <NSNumber *>*)sourceArray {
[sourceArray sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
NSNumber *objModel1 = obj1;
NSNumber *objModel2 = obj2;
CGFloat ret = [objModel2 floatValue] - [objModel1 floatValue];
if (ret > 0) {
return NSOrderedAscending;//升序
}
else if (ret < 0){
return NSOrderedDescending;//降序
}
else {
return NSOrderedSame;
}
}];
}
/**
* 快速排序
**/
- (void)quickSort:(NSMutableArray <NSNumber *>*)sourceArray
withLeft:(NSInteger)left
andRight:(NSInteger)right {
//数组不需要排序
if (left >= right) return;
//数组第一个位置
NSInteger i = left;
//数组最后一个位置
NSInteger j = right;
//将第一个位置的<value>作为---基准
NSInteger pivot = [sourceArray[left] integerValue];
while (i != j) {
//从后往前走, 直到找到 大于 <基准> 的数字, 此时 j 保存那个数字的下标位置
while (i < j && pivot <= [sourceArray[j] integerValue]) {
j--;
}
//再从前往后走, 直到找到 小于 <基准> 的数字, 此时 i 保存那个数字的下标位置
while (i < j && pivot >= [sourceArray[i] integerValue]) {
i++;
}
//互换位置
if (i < j) {
[sourceArray exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
//最终将基准数归位, 因为i == j, 需要将<基数所在位置的value>与<i/j相等的位置的value>互换位置
[sourceArray exchangeObjectAtIndex:i withObjectAtIndex:left];
//继续左边的排序
[self quickSort:sourceArray withLeft: left andRight:i - 1];
//继续右边的排序
[self quickSort:sourceArray withLeft: i + 1 andRight:right];
}
/**
* 冒泡排序
**/
- (void)buddleSort:(NSMutableArray *)sourceArray {
if (sourceArray == nil || sourceArray.count == 0) {
return;
}
for (int i = 0; i < sourceArray.count; i++) {
for (int j = 0; j < sourceArray.count - i; j++) {
if ([sourceArray[j] compare:sourceArray[j+1]] == NSOrderedDescending) {
[sourceArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
}
/**
* 选择排序
**/
- (void)selectSort:(NSMutableArray <NSNumber *>*)sourceArray {
for (int i = 0; i < sourceArray.count; i++ ) {
for (int j = i + 1; j < sourceArray.count; j++ ) {
if ([sourceArray[i] compare:sourceArray[j]] == NSOrderedDescending) {
[sourceArray exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
/**
* 插入排序
**/
- (void)inserSort:(NSMutableArray *)sourceArray {
if(sourceArray == nil || sourceArray.count == 0){
return;
}
for (int i = 0; i < sourceArray.count; i++) {
NSNumber *temp = sourceArray[i];
int j = i-1;
while (j >= 0 && [sourceArray[j] compare:temp] == NSOrderedDescending) {
[sourceArray replaceObjectAtIndex:j+1 withObject:sourceArray[j]];
j--;
//printf("
排序中i == %ld: ",i);
//[self printArray:sourceArray];
}
[sourceArray replaceObjectAtIndex:j+1 withObject:temp];
//[self printArray:sourceArray];
}
}
/**
排序前:5 1 4 2 3
排序中i == 1: 5 5 4 2 3
排序中i == 2: 1 5 5 2 3
排序中i == 3: 1 4 5 5 3
排序中i == 3: 1 4 4 5 3
排序中i == 4: 1 2 4 5 5
排序中i == 4: 1 2 4 4 5
排序完成:1 2 3 4 5
**/
- (void)printArray:(NSArray *)array {
for(NSNumber *number in array) {
printf("%d ",[number intValue]);
}
}
常用的内部排序方法有：
交换排序（冒泡排序、快速排序）、
选择排序（简单选择排序、堆排序）、
插入排序（直接插入排序、希尔排序）、
归并排序、
基数排序（一关键字、多关键字）。
小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，
由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。