排序算法
稳定性：排序算法的
稳定性通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。`对于金额相同的订单，我们希望按照下单时间从早到晚有序`。对于这样一个排序需求，我们怎么来做呢？
最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。借助`稳定`排序算法，这个问题可以非常简洁地解决。
解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。
为什么呢？`稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变`。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。
交换类排序：该类方法的核心是“交换”，即每趟排序，都是通过一系列的“交换”动作完成的，如军训排队时，教官说：你比旁边的高，你俩交换下，还比下一个高就继续交换。这类排序有：冒泡排序、快速排序。
插入类排序 : 即在一个已经有序的序列中，插入一个新的记录，就好比军训排队，已经排好一个纵队，这时来了个新家伙，于是新来的“插入”这个队伍中的合适位置。这类排序有：直接插入排序、折半插入排序、希尔排序。
选择类排序: 该方法的核心是“选择”，即每趟排序都选出一个最小（或最大）的记录，把它和序列中的第一个（或最后一个）记录交换，这样最小（或最大）的记录到位。如军训排队时，教官选出个子最小的同学，让他和第一个位置的同学交换，剩下的继续选择。这类排序有：选择排序、堆排序。
冒泡排序 O(n^2) 稳定
相邻元素两两比较
//4. 冒泡排序-对顺序表L进行交换排序(冒泡排序初级版本)
void BubbleSort0(SqList *L){
int i,j;
for (i = 1; i < L->length; i++) {
for (j = i+1; j <= L->length; j++) {
if(L->r[i] > L->r[j])
swap(L, i, j);
}
}
}
//5.冒泡排序-对顺序表L作冒泡排序(正宗冒泡排序算法)
void BubbleSort(SqList *L){
int i,j;
for (i = 1; i < L->length; i++) {
//注意:这里j是从后面往前循环
for (j = L->length-1; j>=i; j--) {
//若前者大于后者(注意与上一个算法区别所在)
if(L->r[j]>L->r[j+1])
//交换L->r[j]与L->r[j+1]的值;
swap(L, j, j+1);
}
}
}
冒泡排序优化：
1、假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。
2、每次都会有确定的值冒泡到最右边，所以内循环要减去外循环的变量i，以避免不必要的比较。
//6.冒泡排序-对顺序表L冒泡排序进行优化
void BubbleSort2(SqList *L){
int i,j;
//优化点1：flag用作标记
Status flag = TRUE;
//i从[1,L->length) 遍历;
//如果flag为False退出循环. 表示已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态;
for (i = 1; i < L->length && flag; i++) {
//flag 每次都初始化为FALSE
flag = FALSE;
for (j = L->length-1; j>=i; j--) {
if(L->r[j] > L->r[j+1]){
//交换L->r[j]和L->r[j+1]值;
swap(L, j, j+1);
//如果有任何数据的交换动作,则将flag改为true;
flag=TRUE;
}
}
}
}
插入排序 时间：O(n^2) 空间：O(1) 稳定 相对于同样时间复杂度的是冒泡排序(交换数据时三次赋值操作)、选择排序(不稳定)，插入排序是最优选择。
插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。是从一个乱序的数组中依次取值，插入到一个已经排好序的数组中。这看起来好像要两个数组才能完成，但如果只想在同一个数组内排序，也是可以的。
可以理解为一个大循环，每次取未排序的队列中的第一个元素，拿去和已排序的数组进行小循环遍历比较，插入到已排序数组合适的位置。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，都是原地排序算法，在实际的开发里，但我们更倾向于使用插入排序算法而不是冒泡排序算法。因为冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。也就是相同的逆序度N，元素交换、移动的次数是一样的，都是N， 但是冒泡排序元素交换时需要3次赋值操作，而插入排序做元素移动时只需要一次赋值操作
直接插入排序遍历比较时间复杂度是每次O(n),交换的时间复杂度每次也是O(n),那么n次总共的时间复杂度就是O(n^2)。 有人会问折半(二分)插入能否优化成O(nlogn),答案是不能的。因为二分只能减少查找复杂度每次为O(logn),而插入的时间复杂度每次为O(n)级别，这样总的时间复杂度级别还是O(n^2).
void insertion_sort(int arr[], int len){
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];//每次临时从未排序队列里拿出未排序的第一个值
j=i-1;
//将扫描到的数值插入到已排序序列合适的位置，从已经排序的序列「最右边」的开始比较，找到比其小的数
//while或for循环都可以
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];//将数据依次向后移动一位 直到找到合适的位置
j--;
}
arr[j+1] = key;//插入到比前一位大，比后一位小的位置
}
}
// for循环中的 ++i 和 i++没区别
NSMutableArray * arr = [NSMutableArray arrayWithArray:@[@4,@6,@5,@1,@3,@2]];
for (int i = 1 ;i < arr.count ; i ++) {
int value = [arr[i] intValue]; //临时保存要插入的值
int j = i - 1 ;
for (;j >= 0 ; j--) {
if ( value < [arr[j] intValue]) { //依次比较要插入的值value和已排序序列中的值 对比动图理解
arr[j + 1] = arr[j];
}else {
break;
}
}
//这里j会有--操作 如果要插在第0个位置，那么此时j就为 -1
arr[j + 1] = @(value);
}
insertionSort.gif
归并排序 时间：O(nlogn) 空间：O(n) 稳定
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并和快排都是「基于分治算法」的，分治算法其实应用挺多的，很多分治会用到递归，但事实上「分治和递归是两把事」。分治就是分而治之，可以采用递归实现，也可以自己遍历实现非递归方式。而归并排序就是先将问题分解成代价较小的子问题，子问题再采取代价较小的合并方式完成一个排序。
至于归并的思想是这样的：递归二分切分-合并(合并过程中排序)
- 第一次：整串先进行划分成一个一个单独，第一次是将序列中(1 2 3 4 5 6---)两两归并成有序，归并完(xx xx xx xx----)这样局部有序的序列。
- 第二次就是两两归并成若干四个(1 2 3 4 5 6 7 8 ----)「每个小局部是有序的」。
- 就这样一直到最后这个串串只剩一个，然而这个耗费的总次数logn。每次操作的时间复杂的又是O(n)。所以总共的时间复杂度为
O(nlogn). - 表现比选择排序好的多,代价是
需要额外的内存空间。
注意：归并排序的稳定性取决于合并数组时 是否和拆分数组时的顺序相同而决定的。
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
//出了作用于就释放了临时数组了
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作 需要左中右三个位置参数
}
}
//哨兵
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];//先把 左边的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
思考：现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？ 答：可以运用归并排序合并时的思想。
先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存。当然这里的写入和读取要考虑利用内存来降低读写文件的IO消耗，例如写的时候利用一部分内存(say, 一个500m的空间)来缓存一批写入，达到瓶颈后一次性batch写入。
基数排序 稳定
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
简单选择排序 时间：O(n^2) 空间：O(1) 不稳定
简单选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到「已排序序列的末尾」。以此类推，直到所有元素均排序完毕。
而插入排序是每次从无序列表中选取第一个，然后插入到有序列表中合适的位置。
性能：通常来说，交换次数比冒泡排序少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。且当有相同数据时，排序后可能会导致相同数据的前后顺序和排序前不同，这就是其不稳定性。
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i; // 最小位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j; // 记录最小位置
}
}
if (min != i) {
swap(arr, i, min); // 与第i个位置进行交换
}
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
selectionSort.gif
快速排序 时间:O(nlogn) 空间:O(logn) 不稳定
快速排序是对冒泡排序的一种改进，采用递归分治的方法进行求解，是分而治之思想在排序算法上的典型应用。相比于归并排序先递归二分拆分，再创建临时序列排序合并子序列的逻辑，快速排序的逻辑是先左右指针移动找到比pivot大和小的位置交换排序后并返回pivot的位置，然后根据pivot位置递归分治。
算法思想：以军训排队为例，教官说以第一个同学为中心，比他矮的站他左边，比他高的站他右边，这就是一趟快速排序。因此，一趟快速排序是以一个枢轴，将序列分成两部分，枢轴的一边比它小（或小于等于），另一边比它大（或大于等于）。然后再对这两队人递归。
算法性能：快速排序的效率和选取的“枢轴”有关，选取的枢轴越接近中间值，算法效率就越高。快速排序最好情况下时间复杂度为O(nlogn)，待排序列越接近无序，则该算法效率越高，在最坏情况下时间复杂度为O(n*n)，待排序列越接近有序，则该算法效率越低，算法的平均时间复杂度为O(nlogn)。同时需要的辅助空间也多。快速排序排序效率在同为O(N*logN)的几种排序方法中效率较高。可以通过合理地选择 pivot 来避免这种情况。
复杂度里的N是指每次循环都处理了N个数据，然后划分左区和右区相当于是二分logN。
算法思想一：左右交换法
- 选取一个基准点Pivot，此点最左侧(
不包括Pivot)和最右侧(不包括Pivot)标记为L和R。注意：左右交换法的左右指针不能包括Pivot，而填坑法是需要包括Pivot的 - L从左向右寻找比Pivot
大的，R从右向左寻找比Pivot小的，分别找到一个数并停止移动，然后交换这两个数，L和R继续移动，直到相遇(如i < j)。 - 相遇后的
L或R指针的值和基准点Pivot交换，这就完成了第一次快速排序。后面再对得到的两部分分别进行递归。
算法思想二：填坑法
-
选定数列头元素为基准元素pivot，并记住这个位置index，这个位置相当于一个"坑"。
-
设置两个指针left和right，分别指向数列的最左和最右两个元素。
-
接下来从right指针开始，把指针所指向的元素和基准元素做比较，如果比pivot大，则right指针向左移动；如果比pivot小，则把所指向的元素放入index对应的位置。
-
将被放入坑中的元素(right指针移动之前指向的元素)之前的位置赋值给index让这个位置变成一个新的"坑"，同时left指针向右移动一位。
-
接下来切换到left指针进行比较，如果left当前指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把元素放入坑中，left指向的位置赋值给index，使其变成一个新的"坑"，同时right指针向左移动一位。
-
重复步骤3，4，5直到left等于right时，将pivot放入left和right重合的位置，此时数列中比pivot小的元素都在pivot左边，比pivot大的都在pivot元素位置的右边。
-
获取pivot的位置pivotIndex，分而制之，将pivotIndex左侧和右侧的子数列分别重复上述步骤。
//快速排序（目标数组，数组的起始位置，数组的终止位置）
static void QuickSort(int[] array, int left = 0, int right = -1)
{
if (right.Equals(-1)) right = array.Length - 1;
int keyValuePosition; //记录关键值的下标
//当传递的目标数组含有两个以上的元素时，进行递归调用。（即：当传递的目标数组只含有一个元素时，此趟排序结束）
if (left < right)
{
keyValuePosition = Partion(array, left, right); //获取关键值的下标（快排的核心）这里先排序
QuickSort(array, left, keyValuePosition - 1); //递归调用，快排划分出来的左区间
QuickSort(array, keyValuePosition + 1, right); //递归调用，快排划分出来的右区间
}
}
catch (Exception ex)
{
Console.WriteLine("Exception: {0}", ex);
}
}
///快速排序的核心部分：确定关键值在数组中的位置，以此将数组划分成左右两区间，关键值游离在外。（返回关键值应在数组中的下标）
static int Partion(int[] array, int left, int right)
{
int leftIndex = left; //记录目标数组的起始位置（后续动态的左侧下标）
int rightIndex = right; //记录目标数组的结束位置（后续动态的右侧下标）
int keyValue = array[left]; //数组的第一个元素作为关键值
int temp;
//当 （左侧动态下标 == 右侧动态下标） 时跳出循环
while (leftIndex < rightIndex)
{
while (leftIndex < rightIndex && array[leftIndex] <= keyValue) //左侧动态下标逐渐增加，直至找到大于keyValue的下标
{
leftIndex++;
}
while (leftIndex < rightIndex && array[rightIndex] > keyValue) //右侧动态下标逐渐减小，直至找到小于或等于keyValue的下标
{
rightIndex--;
}
//左右指针都停止后，如果满足条件，则交换彼此
if (leftIndex < rightIndex) //如果leftIndex < rightIndex，则交换左右动态下标所指定的值；当leftIndex==rightIndex时，跳出整个循环
{
temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
//当左右两个动态下标相等时（即：左右下标指向同一个位置），此时便可以确定keyValue的准确位置。
//这里是确定pivot的位置是leftIndex还是rightIndex
temp = keyValue;
if (temp < array[rightIndex]) //当keyValue < 左右下标同时指向的值，将keyValue与rightIndex - 1指向的值交换，并返回rightIndex - 1。
{
array[left] = array[rightIndex - 1];
array[rightIndex - 1] = temp;
return rightIndex - 1; //返回pivot位置
}
else //当keyValue >= 左右下标同时指向的值，将keyValue与rightIndex指向的值交换，并返回rightIndex
{
array[left] = array[rightIndex];
array[rightIndex] = temp;
return rightIndex;//返回pivot位置
}
}
quickSort.gif
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
堆排序 O(nlogn) 不稳定
堆其实就是利用完全二叉树的结构来维护的一维数组。
若父亲大孩子小，则这样的堆叫做大顶堆；若父亲小孩子大，这样的堆叫做小顶堆。根据堆的定义，其根节点的值是最大（或最小），因此将一个无序序列调整为一个堆，就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后（或最前），这样有序序列元素增加1个，无序序列中元素减少1个，对新的无序序列重复这样的操作，就实现了序列排序。堆排序中最关键的操作是将序列调整为堆，整个排序的过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树的过程。
以大顶堆为例:
- 下标为i的节点的
父节点下标：(i - 1)/2 整除 - 下标为i的节点的
左孩子下标：i * 2 + 1 - 下标为i的节点的
右孩子下标：i * 2 + 2
堆排序分两步
- 一：
建堆：建立最大堆时是从最后一个非叶子节点开始从下往上调整的，目的是为了把无序序列调整为一个堆结构。 - 二：
排序:变为堆结构就能找出最大(小)值了。把堆顶的元素和堆底的元素互换，此时交换到堆底的元素已经有序了，为最大(小)值，然后对交换到堆顶的节点递归进行维护堆性质，此时堆底元素相当于独立，维护后再将堆顶和堆底-i交换，以此类推就有序了。
/**
* 维护堆的性质 保证符合大顶堆准则
* @param arr 存储堆的数组
* @param n 数组长度
* @param i 待维护节点的下标
*/
void heapify(int arr[], int n, int i) //复杂度logN
{
int largest = i;
int lson = i * 2 + 1;
int rson = i * 2 + 2;
if (lson < n && arr[largest] < arr[lson])
largest = lson;
if (rson < n && arr[largest] < arr[rson])
largest = rson;
if (largest != i)
{
swap(&arr[largest], &arr[i]);
heapify(arr, n, largest);//递归保证其节点下的其他节点都有序
}
}
// 堆排序入口
void heap_sort(int arr[], int n)
{
int i;
// 建堆 先创建自底部的(如果n=10,那么i = 9为最底部节点) 父节点= (i-1)/2 ，这里的i就是 长度n减去1 为最后底部那个节点
for (i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);//从`最后一个非叶子节点`开始`从下往上`
// 排序
for (i = n - 1; i > 0; i--) //次循环复杂度N
{
swap(&arr[i], &arr[0]);
heapify(arr, i, 0); //复杂度 logN 所以总复杂度是NlogN
}
}
堆排序的优点是适合记录数很多的场景，如从1000000个记录中选出前10个最小的，这种情况用堆排序最好，如果记录数较少，则不提倡使用堆排序。
希尔排序 O(n^2 n^3/2 ..) 不稳定
希尔排序(Shell Sort)，也称递减增量排序算法，是插入排序的一种更高效的改进版本，适用于小规模,部分有序.
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
希尔排序需要用到一个不断缩减的增量序列值，如n/2,即5，3，1,即第一次每隔5个取值去插入排序。第二次每隔3个取值去插入排序，以此类推。
表格.png
结论：
（1）快速排序、希尔排序、归并排序、堆排序的平均时间为O(nlogn)，其他的为O(n*n)。
（2）快速排序、希尔排序、选择排序、堆排序不稳定，其他的稳定。
（3）经过一趟排序能够保证一个元素到达最终位置的是冒泡排序、快速排序、选择排序、堆排序。
（4）元素比较次数和原始序列无关的是选择排序、折半插入排序。
（5）排序趟数和原始序列有关的是交换类排序。
（6）直接插入排序和折半插入排序的区别是寻找插入位置的方式不同，一个是按顺序查找方式，另一个是按折半查找方式。
（7）冒泡、选择、插入排序算法，都是基于数组实现的。如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？
这个答案应该有个前提，即是否允许修改链表的节点value值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。
如何判断单链表是否成环以及环起点。
链表是要类似于6形状，不然圆形的肯定无法判断起点在哪。
- 最简单的方法是创建一个哈希表，将每个节点的地址都存储起来，如果某个节点的地址出现在了哈希表中，那么首次出现的那个节点就是我们要找的成环的起点了。这样时间和空间复杂度都是O(N)。
- 对于单链表来说，我们就可以用两个指针，一个快指针2，一个慢指针1，从起点出发，快指针如果在出发后追上了慢指针，那就说明单链表是
存在环的。寻找起点：假设环形链表的长度是L,相遇点在M,在相遇之后，只需要将fast指针指向开始的节点，然后和slow指针保持同一的速度遍历(相当于此时不分快慢,每个指针的每次步长为1),下一次两个节点相遇的时候就是链表的环形入口。
