常见的六种排序算法
2016-06-27 本文已影响221人
lyking
| 排序算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.5) | O(1) | 不稳定 |
| 选择排序 | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(N*logN) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(N*logN) | O(N*logN) | 不稳定 |
| 归并排序 | O(N*logN) | O(1) | 稳定 |
算法一：插入排序
插入排序算法.png
插入排序（Insertion Sort）在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
时间复杂度： O(n^2)
步骤如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置5. 将新元素插入到该位置中
- 重复步骤2
示例
#pragma mark -- 插入排序---
- (NSMutableArray *)insertSort:(NSMutableArray *)fromArray {
for (int i = 1; i < fromArray.count; i ++)
{
for (int j = i ; j > 0; j --)
{
if ([fromArray[j] integerValue] < [fromArray[j - 1] integerValue])
{
NSNumber *temp = fromArray[j];
fromArray[j] = fromArray[j - 1];
fromArray[j - 1] = temp;
}
else
{
break;
}
}
}
return fromArray;
}
算法二：选择排序
选择排序.png
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
时间复杂度： O(n^2)
步骤如下：
- 遍历数组，找到最小的元素，将其置于数组起始位置。
- 从上次最小元素存放的后一个元素开始遍历至数组尾，将最小的元素置于开始处。
- 重复上述过程，直到元素排序完毕。
示例
#pragma mark ---选择排序---
- (NSMutableArray *)selectSort:(NSMutableArray *)fromArray {
for (int i = 0; i < fromArray.count - 1; i ++)
{
for (int j = i + 1; j < fromArray.count; j++)
{
if ([fromArray[i] integerValue] > [fromArray[j] integerValue])
{
NSNumber *temp = fromArray[i];
fromArray[i] = fromArray[j];
fromArray[j] = temp;
}
}
}
return fromArray;
}
算法三：冒泡排序
冒泡排序.jpg
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
时间复杂度： O(n^2)
步骤如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个，直到把最大的元素放到数组尾部。
- 遍历长度减一，对剩下的元素从头重复以上的步骤。
- 直到没有任何一对数字需要比较时完成。
示例
#pragma mark -- 冒泡排序----
- (NSMutableArray *)bubbleSort:(NSMutableArray *)fromArray {
for (int i = 0; i < fromArray.count; i++)
{
for (int j = 0; j < fromArray.count - 1 - i ; j++)
{
if ([fromArray[j + 1] integerValue] < [fromArray[j] integerValue])
{
NSNumber *temp = fromArray[j + 1];
fromArray[j + 1] = fromArray[j];
fromArray[j] = temp;
}
}
}
return fromArray;
}
算法四：希尔排序
希尔排序.png
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
时间复杂度： O(n^1.5)
步骤如下：
- 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
- 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
示例
#pragma mark --- 希尔排序---
- (NSMutableArray *)shellSort:(NSMutableArray *)fromArray {
NSInteger incre = fromArray.count/2; //增量
while (incre > 0)
{
for (int i = 0; i < incre; i ++) //根据增量分为若干子序列
{
for (int j = i ; j < fromArray.count; j += incre) //分组内插入排序
{
for (int k = j ; k > i; k -= incre)
{
if ([fromArray[k] integerValue] < [fromArray[k - incre] integerValue])
{
NSNumber *temp = fromArray[k];
fromArray[k] = fromArray[k - incre];
fromArray[k - incre] = temp;
}
else
{
break;
}
}
}
}
incre /= 2;
}
return fromArray;
}
算法五：快速排序
快速排序.gif
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度：O(N*logN)
步骤：
- 从数列中挑出一个元素，称为 “基准”（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
示例
#pragma mark ----- 快速排序 ---
- (NSMutableArray *)quickSork:(NSMutableArray *)fromArray {
NSMutableArray *leftArray = [NSMutableArray array];
NSMutableArray *rightArray = [NSMutableArray array];
if (fromArray.count < 1)
{
return fromArray;
}
//随机一个基点
int randomPivotPoint = arc4random() % fromArray.count;
NSNumber *pivotValue = fromArray[randomPivotPoint];
[fromArray removeObject:pivotValue];
for (NSNumber *num in fromArray)
{
if ([num integerValue] < [pivotValue integerValue])
{
[leftArray addObject:num];
}
else
{
[rightArray addObject:num];
}
}
//递归
NSMutableArray *sortArray = [NSMutableArray array];
[sortArray addObjectsFromArray:[self quickSork:leftArray]];
[sortArray addObject:pivotValue];
[sortArray addObjectsFromArray:[self quickSork:rightArray]];
return sortArray;
}
算法六：归并排序
归并算法.png
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
时间复杂度：O(N*logN)
步骤如下：
- 申请空间，创建两个数组，长度分别为两个有序数组的长度
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
示例
#pragma mark --- 归并排序 ------
- (void)mergeSort:(NSMutableArray *)list startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex{
if (startIndex < endIndex)
{
//取中间位置，将左右两边分别递归进行归并，直至左右两边只剩1个元素
NSInteger middle = (startIndex + endIndex) / 2;
[self mergeSort:list startIndex:startIndex endIndex:middle];
[self mergeSort:list startIndex:middle+1 endIndex:endIndex];
//对左右2边的数据进行合并
NSInteger i = startIndex; //左边数据的起始位置
NSInteger j = middle+1; //右边数据的起始位置
NSMutableArray *temp = [NSMutableArray array]; //临时数组
while (i <= middle && j <= endIndex)
{
//如果左边数据较小，则将其放到临时数组里，并将左边位置向后移一位
if ([list[i] integerValue] < [list[j] integerValue])
{
[temp addObject:list[i]];
i++;
}
//否则将右边数据放到临时数组里，并将右边位置向后移一位
else
{
[temp addObject:list[j]];
j++;
}
}
//如果左边还有数据，则将剩余的部分全都复制到临时数组里
while (i <= middle)
{
[temp addObject:list[i]];
i++;
}
//如果右边还有数据（左右两边只可能存在一边有剩余数据的情况），则将剩余的部分全都复制到临时数组里
while (j <= endIndex)
{
[temp addObject:list[j]];
j++;
}
//再将临时数组里的数据（已经排好序了）保存到原始数据中，以达到对原始数据的排序
for (i=0; i < temp.count; i++)
{
//注意：需要从startIndex位置开始，因为这里是递归调用的
[list replaceObjectAtIndex:startIndex withObject:temp[i]];
startIndex++;
}
}
}
算法七：堆排序
堆排序.png
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
时间复杂度：O(N*logN) 由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。
步骤如下：
- 将数据初始化成堆，即将数据存储到一个完全二叉树中，再构造大顶堆（升序）或小顶堆（降序）。
- 交换堆顶元素和最后一个元素，得到一个新的堆，被交换到底部的黄色部分为有序，其余堆为无序且可能不满足堆特性，所以需要对其余部分进行堆调整，调整好后继续将堆顶元素和最后一个堆低未排序元素进行交换……
示例
#pragma mark ---- 堆排序 -------
/**
* array: 数据源
* index: 节点索引
*/
-(void)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index length:(NSInteger)length
{
NSInteger leftChildIndex = index * 2 + 1; //获取该节点的左子节点索引
NSInteger rightChildIndex = index * 2 + 2; //获取该节点的右子节点索引
NSInteger maxValueIndex = index;//暂时把该索引当做最大值所对应的索引
//判断左子节点的值是否大于当前最大值
if (leftChildIndex < length && [array[leftChildIndex] integerValue] > [array[maxValueIndex] integerValue])
{
//把左子节点的索引作为最大值所对应的索引
maxValueIndex = leftChildIndex;
}
//判断右子节点的值是否大于当前最大值
if (rightChildIndex < length && [array[rightChildIndex] integerValue] > [array[maxValueIndex] integerValue])
{
maxValueIndex = rightChildIndex;
}
//如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
if (maxValueIndex != index)
{
[array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
}
}
//构建最大栈
- (void)createMaxHeap:(NSMutableArray*)array
{
/*
从最后一个非叶子节点开始 自下而上进行调整堆
*/
for (NSInteger i = (array.count/2 - 1);i >= 0; --i)
{
[self maxHeapAdjust:array index:i length:array.count] ;
}
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(int j = array.count - 1;j > 0; --j)
{
//把第一个元素和当前的最后一个元素交换，
[array exchangeObjectAtIndex:0 withObjectAtIndex:j];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
[self maxHeapAdjust:array index:0 length:j];
}
}
//最大栈排序
- (void)maxHeapSort:(NSMutableArray *)fromArray
{
[self createMaxHeap:fromArray];
}
---------第二部分:链表-------------
判断一个链表是否有环
声明一个节点
typedef int ElemType; // 假定数据类型为int
typedef struct Node{
ElemType data;
struct Node *next;
} Node,*LinkList;
代码实现
#pragma mark ------------链表----------------
#pragma mark ------ 判断一个链表是否有环 -----
//如何判断是否有环？如果有两个头结点指针，一个走的快，一个走的慢，那么若干步以后，快的指针总会超过慢的指针一圈。
- (BOOL)hasLoop:(LinkList)pHead{
LinkList fast,slow;
fast = pHead;
slow = pHead;
//如果无环，则fast先走到终点
//当链表长度为奇数时，fast->Next为空
//当链表长度为偶数时，fast为空
while (fast != NULL && fast -> next != NULL)
{
fast = fast -> next -> next;
slow = slow -> next;
//如果有环，则fast会超过slow一圈
if (fast == slow)
{
break;
}
}
if (fast == NULL || fast -> next == NULL)
{
return NO;
}
else
return YES;
}
Every day to write, to be continued...
