1.冒泡排序
- 重复的比较数组中相邻的两个元素。如果一个元素比另一个元素大（小），那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟，每一趟比较n-j次，j是已经排序好的元素个数。
- 每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。
- 平均时间复杂度 O(n^2)，最差时间复杂度 O(n^2)
for(int i = 0; i < num-1; i++) {
for(int j = 0; j < num - 1 - i; j++) {
if(array[j] < array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
2.选择排序
- 从数组的第i个元素开始到第n个元素，从i+1到n寻找最小的元素。将找到的最小元素和第i位元素交换。
- 平均时间复杂度 O(n^2)，最差时间复杂度 O(n^2)
for(int i = 0; i < num-1; i++) {
for(int j = i+1; j < num - 1; j++) {
if(array[i] < array[j]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
3､插入排序
- 取i作为元素，认为i-1之前都已经排好序，从后向前扫描
- 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置，重复该步骤直到已排好序的元素小于或等于新元素。在当前位置插入新元素
- 平均时间复杂度 O(n^2)，最差时间复杂度 O(n^2)
for(int i = 1; i < num-1; i++) {
int temp = array[i];
for(int j = i-1; j >= 0 && temp < array[j]; j--) {
array[j+1] = array[j];
array[j]= temp;
}
}
4.快速排序 (原理解析 https://blog.csdn.net/yzllz001/article/details/50982841)
- 快速排序使用分治策略来把一个串行分为两个子串行。
- 从数列中挑出一个元素，称为 “基准”（pivot）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 在每次的迭代（iteration）中，它会“基准”元素摆到它最后的位置去。
- 平均时间复杂度 O(nlogN)，最差时间复杂度 O(n^2)
void quicksort(int left,int right)
{
int i,j,t,temp;
if (left>right) return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
//顺序很重要，要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找右边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if (i<j) {
t=a[i]; a[i]=a[j]; a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}
快排退化成O(N^2)
-
这个答案还得看枢轴（pivot）的选择策略。在快速排序的早期版本中呢，最左面或者是最右面的那个元素被选为枢轴，那最坏的情况就会在下面的情况下发生啦：
1）数组已经是正序（same order）排过序的。
2）数组已经是倒序排过序的。
3）所有的元素都相同（1、2的特殊情况）因为这些案例在用例中十分常见，所以这个问题可以通过要么选择一个随机的枢轴，或者选择一个分区中间的下标作为枢轴，或者（特别是对于相比更长的分区）选择分区的第一个、中间、最后一个元素的中值作为枢轴。有了这些修改，那快排的最差的情况就不那么容易出现了，但是如果输入的数组最大（或者最小元素）被选为枢轴，那最坏的情况就又来了。
5.堆排序 (https://www.jianshu.com/p/938789fde325)
- 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)
- 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
//给定父节点的索引，得到左子节点的索引
#define LeftChild(i) (2*(i)+1)
//元素下沉方法
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 (A[i]<A[child])
{
//交换当前父节点处的元素值与较大子节点的元素值
tmp= A[i];
A[i] = A[child];
A[child] = tmp;
}
else
{
break;
}
}
}
//堆排序
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 Swap(int *num1, int * num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//主函数
void main()
{
int A[6] = {4,5,3,2,6,1};
HeapSort(A, 6);
}
6.归并排序
- 设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
7.希尔排序
8.基数排序
常见问题：
100万以内的质数，怎么筛
欧拉筛法： 当一个数为素数的时候，它的倍数肯定不是素数。所以我们可以从2开始通过乘积筛掉所有的合数。将所有合数标记，保证不被重复筛除，时间复杂度为O（n）。
保证一个合数只被筛一次：任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。
当i是prime[j]的整数倍时（i % prime[j] == 0），i*prime[j+1]肯定被筛过，跳出循环
bool IsPrime[10000001];
int Pri[2000001],PriN;
int FindPrime ( int MaxN ) {
for( int i = 2 ; i <= MaxN ; ++i ){
if( IsPrime[ i ] )
Pri[ PriN++ ]=i; //将这句话放在下面的循环前以保证PriN和Pri值的完整性
for(int j=0;j<PriN;++j){
if( i*Pri[ j ] > MaxN )
break; //当过大了就跳出
IsPrime[ i * Pri[ j ] ] = 0;
//筛去素数
if( i % Pri[ j ] == 0 ) break;
//这里是关键,如果i是一个合数(这当然是允许的)而且i mod prime[j] = 0
//那么跳出,因为i*prime[ (- over -)j ]一定已经被筛去了,被一个素因子比i小的数
}
}
}
堆排，快排，什么区别
在真实情况下， 一般快排的效率比堆排序高很多。
快排：数组中交换数据，在数据量不是特别大，而且离散程度较高的情况下效率很高
堆排序：创建堆，数据交换，调整堆的时间均很多
所以在实际应用中，我们用快排会更多一点。
堆排序的典型应用：在100万个数字中找出最大的100个这种问题，构建一个小顶堆然后遍历调整就可以了
为什么是小顶堆：小顶堆，最小的数就在最上面，只要与最上面的数进行比较就可以了，所以是小顶
topK问题 (维护K大小的最小堆)
https://blog.csdn.net/will130/article/details/49635429
https://www.cnblogs.com/xudong-bupt/archive/2013/03/20/2971262.html
