iOS 排序相关复习

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