排序算法
经历了两次面试，可能我的问题还是在于记忆和表达，有的东西其实是会的，你给我问题我能解决，也知道怎么在合适的时候应用合适的解决方案，但是面试的时候往往无法表达出，面试需要的能力往往和学习的能力不太一样。
所以我想写一下博客，把知识点整理一下，顺便练一下表达的能力，以后每次面试前来看一看。
插入排序
插入排序就是把一组数据分为两个部分，一部分是有序的，一部分是无序的，最初有序部分大小为一，然后每次从无序列表中拿出一个数插入到有序列表中，直到无序列表中的值耗尽，这就是插入排序。
代码描述，还是书上的算法比较好，我最近真的不知道百度搜索怎么回事，搜索出来的内容质量太低了，搜算法搜出来都是错的，乱讲一堆瞎带节奏。
void insertSort(int a[], int n)
{
int j, P;
int tmp;
for(P=1; P<n; P++)
{
tmp = a[P];
for(j=P; j>0 && a[j-1]>tmp; j--)
{
a[j] = a[j-1];
}
a[j] = tmp;
}
} 这个算法非常简单清晰，首选我们取位置P的值，然后我们在位置0到P之间找遍历，并且不断地把这之间的值向后移一位，找到合适的位置将值插入进去。 这个就是插入排序，它的复杂度分析，最优复杂度是O(N)，最差复杂度是O(N2)，为什么呢，如果我们将一组排好序的数组放进去，那么每次遍历到值a[P]，内层for循环不会进去，因为a[j-1] < tmp，所以复杂度是O(N)，但若是最坏情况下，全是逆序的情况下，复杂度是O(N2)，但是平均条件下呢，这就源于一个定理，N个互异的数组的平均逆序数是N(N-1)/4。而插入排序的运行时间是O(I+N),其中I为原始数组中的逆序数。
还有一个定理，通过交换相邻元素进行排序的任何算法平均需要Ω(N2)。这条定理能够证明许多算法的复杂度。
希尔排序
void shellSort(int a[], int n)
{
int i, j, Increment;
int tmp;
for(Increment = n/2; Increment > 0; Increment /= 2)
{
for(i = Increment; i<n; i++)
{
tmp = a[i];
for(j = i; j >= Increment; j -= Increment)
{
if(tmp < a[j - Increment])
{
a[j] = a[j-Increment];
}
else
break;
}
a[j] = tmp;
}
}
} 希尔排序实质上也是插入排序只不过对象不同，插入排序针对的是相隔 hk 的元素序列，一趟过后所有相隔hk 的元素都会被排序。 希尔排序的复杂度分析很难，根据增量序列的不同，有所变化，使用希尔增量时，希尔排序的最坏运行时间为O(N2)，使用Hibbard增量时，希尔排序的最坏情形运行时间为O(N3/2)。
堆排序
void PercDown(int a[], int i, int n)
{
int child;
int tmp;
for(tmp = a[i]; LeftChild(i)<n; i = child)
{
child = LeftChild(i);
if(child != n - 1 && a[child + 1] > a[child])
child++;
if(tmp < a[child])
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
void heapSort(int a[], int n)
{
int i;
for(i = n/2; i>=0; i--)
{
PercDown(a, i, n);
}
for(i = n-1; i>0; i--)
{
swap(a[0], a[i]);
PercDown(a, 0, i);
}
} 堆排序的思想很简单，就是维护一个堆，每次从堆中取出最大的值放到最后。
堆排序总的运行时间是O(NlogN)。 归并排序
void Merge(int a[], int tmpArray[], int Lpos, int Rpos, int rightEnd)
{
int i, leftEnd, numElements, tmpPos;
leftEnd = Rpos - 1;
tmpPos = Lpos;
numElements = rightEnd - Lpos + 1;
while(Lpos <= leftEnd && Rpos <= rightEnd)
{
if(a[Lpos] <= a[Rpos])
tmpArray[tmpPos++] = a[Lpos++];
else
tmpArray[tmpPos++] = a[Rpos++];
}
while(Lpos <= leftEnd)
tmpArray[tmpPos++] = a[Lpos++];
while(Rpos <= rightEnd)
tmpArray[tmpPos++] = a[Rpos++];
for(i = 0; i < numElements; i++, rightEnd--)
a[rightEnd] = tmpArray[rightEnd];
}
void MSort(int a[], int tmpArray[], int left, int right)
{
int center;
if(left < right)
{
center = (left + right)/2;
MSort(a, tmpArray, left, center);
MSort(a, tmpArray, center+1, right);
Merge(a, tmpArray, left, center+1, right);
}
}
void mergeSort(int a[], int n)
{
int *tmpArray;
tmpArray = (int*)malloc(n*sizeof(int));
if(tmpArray != NULL)
{
MSort(a, tmpArray, 0, n-1);
free(tmpArray);
}
} 归并排序的思想很简单，就是把两个有序的列表合并为一个有序的列表，利用递归不断的把大的问题分解为小问题，最终当列表只有一个元素时，它肯定是有序的，然后回溯到上一个问题，merge合并，这样不断地递归，合并，最终得到了一个完整的有序的列表。 归并排序以O(NlogN)最坏情形运行时间运行。
冒泡排序
void bubbleSort(int a[], int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j] > a[j+1])
{
int tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
}
}
}
} 冒泡排序，冒泡就完事，复杂度O(N2)，宿命啊。 快速排序
int Median3(int a[], int left, int right)
{
int center = (left+right)/2;
if(a[left] > a[center])
swap(a[left], a[center]);
if(a[left] > a[right])
swap(a[left], a[right]);
if(a[center] > a[right])
swap(a[center], a[right]);
swap(a[center], a[right-1]);
return a[right-1];
}
#define cutoff (3)
void Qsort(int a[], int left, int right)
{
int i, j;
int pivot;
if(left + cutoff <= right)
{
pivot = Median3(a, left, right);
i = left, j = right - 1;
for( ; ; )
{
while(a[++i] < pivot) {}
while(a[--j] > pivot) {}
if(i < j)
swap(a[i], a[j]);
else
break;
}
swap(a[i], a[right-1]);
Qsort(a, left, i - 1);
Qsort(a, i + 1, right);
}
else
insertSort(a+left, right-left+1);
}
void QuickSort(int a[], int n)
{
Qsort(a, 0, n-1);
} 快速排序平均运行时间是O(NlogN)，最坏情形的性能为O(N2)。 选择排序
void selectionSort(int a[], int n)
{
int Min, tmp;
for(int i=0; i<n; i++)
{
Min = i;
for(int j=i+1;j<n;j++)
{
if(a[j] < a[Min])
{
Min = j;
}
}
if(Min != i)
{
tmp = a[i];
a[i] = a[Min];
a[Min] = tmp;
}
}
} 选择排序，选就完事，复杂度O(N2)，交换相邻元素排序算法的宿命。
算法稳定性分析
为什么稳定不知道，背就完事
全部代码
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<string.h>
using namespace std;
#define LeftChild(i) (2*(i) + 1)
void insertSort(int a[], int n)
{
int j, P;
int tmp;
for(P=1; P<n; P++)
{
tmp = a[P];
for(j=P; j>0 && a[j-1]>tmp; j--)
{
a[j] = a[j-1];
}
a[j] = tmp;
}
}
void shellSort(int a[], int n)
{
int i, j, Increment;
int tmp;
for(Increment = n/2; Increment > 0; Increment /= 2)
{
printf("Increment = %d\n", Increment);
for(i = Increment; i<n; i++)
{
tmp = a[i];
for(j = i; j >= Increment; j -= Increment)
{
if(tmp < a[j - Increment])
{
printf("%d %d\n", j, j-Increment);
a[j] = a[j-Increment];
}
else
break;
}
a[j] = tmp;
}
}
}
void PercDown(int a[], int i, int n)
{
int child;
int tmp;
for(tmp = a[i]; LeftChild(i)<n; i = child)
{
child = LeftChild(i);
if(child != n - 1 && a[child + 1] > a[child])
child++;
if(tmp < a[child])
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
void heapSort(int a[], int n)
{
int i;
for(i = n/2; i>=0; i--)
{
PercDown(a, i, n);
}
for(i = n-1; i>0; i--)
{
swap(a[0], a[i]);
PercDown(a, 0, i);
}
}
void Merge(int a[], int tmpArray[], int Lpos, int Rpos, int rightEnd)
{
int i, leftEnd, numElements, tmpPos;
leftEnd = Rpos - 1;
tmpPos = Lpos;
numElements = rightEnd - Lpos + 1;
while(Lpos <= leftEnd && Rpos <= rightEnd)
{
if(a[Lpos] <= a[Rpos])
tmpArray[tmpPos++] = a[Lpos++];
else
tmpArray[tmpPos++] = a[Rpos++];
}
while(Lpos <= leftEnd)
tmpArray[tmpPos++] = a[Lpos++];
while(Rpos <= rightEnd)
tmpArray[tmpPos++] = a[Rpos++];
for(i = 0; i < numElements; i++, rightEnd--)
a[rightEnd] = tmpArray[rightEnd];
}
void MSort(int a[], int tmpArray[], int left, int right)
{
int center;
if(left < right)
{
center = (left + right)/2;
MSort(a, tmpArray, left, center);
MSort(a, tmpArray, center+1, right);
Merge(a, tmpArray, left, center+1, right);
}
}
void mergeSort(int a[], int n)
{
int *tmpArray;
tmpArray = (int*)malloc(n*sizeof(int));
if(tmpArray != NULL)
{
MSort(a, tmpArray, 0, n-1);
free(tmpArray);
}
}
void bubbleSort(int a[], int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j] > a[j+1])
{
int tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
}
}
}
}
void selectionSort(int a[], int n)
{
int Min, tmp;
for(int i=0; i<n; i++)
{
Min = i;
for(int j=i+1;j<n;j++)
{
if(a[j] < a[Min])
{
Min = j;
}
}
if(Min != i)
{
tmp = a[i];
a[i] = a[Min];
a[Min] = tmp;
}
}
}
int Median3(int a[], int left, int right)
{
int center = (left+right)/2;
if(a[left] > a[center])
swap(a[left], a[center]);
if(a[left] > a[right])
swap(a[left], a[right]);
if(a[center] > a[right])
swap(a[center], a[right]);
swap(a[center], a[right-1]);
return a[right-1];
}
#define cutoff (3)
void Qsort(int a[], int left, int right)
{
int i, j;
int pivot;
if(left + cutoff <= right)
{
pivot = Median3(a, left, right);
i = left, j = right - 1;
for( ; ; )
{
while(a[++i] < pivot) {}
while(a[--j] > pivot) {}
if(i < j)
swap(a[i], a[j]);
else
break;
}
swap(a[i], a[right-1]);
Qsort(a, left, i - 1);
Qsort(a, i + 1, right);
}
else
insertSort(a+left, right-left+1);
}
void QuickSort(int a[], int n)
{
Qsort(a, 0, n-1);
}
void print(int a[], int n)
{
for(int i=0;i<n;i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[16] = {1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16};
//insertSort(a, 10);
//shellSort(a, 16);
//heapSort(a, 16);
//mergeSort(a, 16);
//bubbleSort(a, 16);
//selectionSort(a, 16);
QuickSort(a, 16);
print(a, 16);
}