数据结构排序复习 OC实现
一、内部排序和外部排序
由于待排序的记录数量不同，使得排序过程中的涉及的存储器不同，可将排序方法分为内部排序和外部排序；
内部排序是指：待排序的记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序的记录的数量很大，以至于内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、内部排序的几种排序方式
1、直接插入排序
直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
也就是说：把序列的第一条记录看做一个有序表，从第二个开始进行插入排序，到第几个之前，前面的记录应该都是有序的。
上OC代码：
//直接插入排序
- (void)sortArrWithInsertSort:(NSMutableArray *)arr{
NSLog(@"%@",arr);
int currentLocation = 1; //记录当前位置(哨兵)
//从第1个元素开始取，第0个元素默认为有序的序列
for (int i = 1; i < arr.count ; i++) {
int tempNum = [[arr objectAtIndex:i] intValue];
currentLocation = i;
for (int j = i-1; (tempNum < [[arr objectAtIndex:j] intValue])&&j>=0; j--) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:currentLocation];
currentLocation = j;
}
}
NSLog(@"%@",arr);
}
最好的情况：都是顺序,外层循环执行n-1次，第二层循环都要走一次 ，两层循环是(n-1)*1,时间复杂度为O(n);
最坏的情况：都是倒序,时间复杂度O(n2);
注：当n很小时，这是一种很好的排序方法，但是当n很大时就不宜采用插入排序，以下两种是对插入排序的改进。
1.1折半插入排序
在有序表中取low就是1,height = i-1,先进行折半查找middle = (1+i-1)/2 ,如果当前要排序的元素大于middle的位置的元素，那么low = middle+1;否则height = middle-1;
oc代码实现如下：
//折半插入排序
- (void)sortArrWithHalfInsertSort:(NSMutableArray *)arr{
NSLog(@"%@",arr);
int currentLocation;
for (int i = 1; i < arr.count; i++) {
int low = 0;
currentLocation = i;
int height = i-1;
int tempNum = [[arr objectAtIndex:i] intValue];
while (low <= height) {
int middle = (low + height)/2;
if (tempNum < [arr[middle] intValue]) {
height = middle - 1;
}else{
low = middle + 1;
}
}
for (int j = i-1; j >= low; j--) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:currentLocation];
currentLocation = j;
}
}
NSLog(@"%@",arr);
}注：c语言算法中是arr[0]作为监视哨，和j--元素依次相比，如果小于那么当前j元素要向j+1个位置移，直到最后把arr[0]应该插入的位置空出来放进去；这里使用OC语言，直接设立currentLocation来记录当前元素移动到哪里，没有做后移操作，直接交换位置;
折半插入减少了比较次数，比较次数变为n倍的以2为底n的对数O(nlog2n);移动次数仍然为O(n2),所以整体的时间复杂度仍然为O(n2);
2、希尔排序(缩小增量排序法)
算法思路：先将整个待排序记录序列分割成若干个子序列，分别进行直接插入排序，待整个序列的记录“基本有序”时,再对全体记录进行一次直接插入排序；
OC代码实现如下：
//希尔排序
- (void)sortArrWithShellSort:(NSMutableArray *)arr{
int gap = (int)arr.count/2; //增量
int tempNum;
while (gap>=1) {
for (int i = gap; i < arr.count; i++) {
tempNum = [arr[i] intValue]; //暂存单元
int j;
for (j = i; j>=gap&&tempNum<[arr[j-gap] intValue]; j = j-gap) {
[arr replaceObjectAtIndex:j withObject:arr[j-gap]]; //子序列排序
}
[arr replaceObjectAtIndex:j withObject:@(tempNum)];
}
gap=gap/2;
}
NSLog(@"%@",arr);
}希尔排序的时间复杂度降到了O(n3/2) ,n的二分之三次幂
3、快速排序
3.1 起泡排序
算法思路：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字，以此类推，直至第N-1条记录和第N条记录的关键字进行比较为止。
OC代码实现如下：
- (void)sortArrWithBubbleSort:(NSMutableArray *)arr{
for (int i = 0; i < arr.count; i++) { //趟数
for (int j= 0; j < arr.count- i - 1; j++) {//相邻元素的比较
if ([[arr objectAtIndex:j] intValue]>[[arr objectAtIndex:j+1] intValue]) {
[arr exchangeObjectAtIndex:j+1 withObjectAtIndex:j];
}
}
}
NSLog(@"%@",arr);
}3.2快速排序
快速排序是对起泡排序的一种改进。
算法思路：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。
OC实现如下：
//快速排序
- (void)sortArrWithQSort:(NSMutableArray *)arr andLow:(int)low andHeight:(int)height{
int pivotkey = [arr[low] intValue];
BOOL direction = NO;
BOOL isOrder = YES;
int p1 = low;
int p2 = height;
if (height - low <= 1) {
return;
}
while (p1 < p2) {
isOrder = YES;
if (direction) {
for (int i = p1; i < p2; i++) { //左往右移
if ([arr[i] intValue] >= pivotkey) {
arr[p2--] = arr[i];
p1 = i;
direction = ! direction;
isOrder = NO;
break;
}
}
if (isOrder) {
p1 = p2;
}
}else{
for (int i = p2; i > p1; i--) { //右往左移
if (pivotkey >= [arr[i] intValue]) {
arr[p1++] = arr[i];
p2 = i;
direction = ! direction;
isOrder = NO;
break;
}
}
if (isOrder) {
p1 = p2;
}
}
}
[arr replaceObjectAtIndex:p1 withObject:@(pivotkey)];
//递归回来
[self sortArrWithQSort:arr andLow:low andHeight:p1-1]; //递归比枢轴小的序列
[self sortArrWithQSort:arr andLow:p1+1 andHeight:height]; //递归比枢轴大的序列
NSLog(@"%@",arr);
}
快速排序的平均时间为Tavg(n) = knlnn，其中n为待排序序列中记录的个数，k为某个常数，经验证明，在所以同数量级的此类(先进的)排序中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序是目前被认为是最好的内部排序方法。
3.3选择排序
基本思路：每一趟在n-i+1(i=1,2,3….,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。（在每一次排序中选出最小的拿到序列的前边）。
3.3.1简单选择排序
算法思路：每一趟找出序列中最小的元素放在待排序列的最前方；
OC代码如下：
//选择排序
- (void)sortArrWithSelectSort:(NSMutableArray *)arr{
for (int i = 0; i <arr.count; i++) {
int tempMin = [arr[i] intValue];
for (int j = i+1; j < arr.count; j++) {
if (tempMin > [arr[j] intValue]) {
tempMin = [arr[j] intValue];
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"%@",arr);
}3.3.2堆排序
基本思路：1、创建大顶堆序列；
2、输出堆顶元素进行堆排序；
3、堆排序内部进行局部调整，左孩子或者右孩子比父节点大的时候要进行局部的调整；
- (void)createMaxHeap:(NSMutableArray *)heapArr{
//创建大顶堆从最后一个非叶子节点 自下而上进行调整堆
for (int i = (int)heapArr.count/2; i>=0; i--) {
heapArr = [self HeapAdjust:heapArr andIndex:i andLength:(int)heapArr.count];
}
//输出根节点元素
int num = (int)heapArr.count;
while (num>1)
{
[heapArr exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
heapArr=[self HeapAdjust:heapArr andIndex:0 andLength:num-1]; //剩余的N-1个序列继续筛选
num--;
}
NSLog(@"%@",heapArr);
}
- (NSMutableArray *)HeapAdjust:(NSMutableArray *)arr andIndex:(int)index andLength:(int)length{
int root = index; //根节点
int left = 2*root + 1; //左子节点
int right = 2*root + 2; //右子节点
if (left<length&&[arr[left] intValue]>[arr[root] intValue]) {
root = left; //左子树大
}
if (right<length&&[arr[right] intValue]>[arr[root] intValue]) {
root = right; //右子树大
}
if (root!=index) {
[arr exchangeObjectAtIndex:root withObjectAtIndex:index];
arr = [self HeapAdjust:arr andIndex:root andLength:length]; //递归调整
}
return arr;
}
注：堆排序在最坏的情况下时间复杂度也为O(nlogn),对于记录较少的情况下不提倡使用，但是对N较大的文件还是很有效的。因为其运行时间主要耗费在建立初始堆和调整新建堆反复的筛选上。
总结：（1）从平均时间性能而言，快速排序最佳，其所需时间最省，但是快速排序在最坏情况下时间性能不如堆排序。
（2）除希尔排序的所有插入排序，起泡排序和简单选择排序，其中以直接插入排序最为简单，当序列的记录基本有序，或N值较小的时候，他是最佳的排序方法，因此经常和其他排序混合使用。