常用排序算法实现

1、常见排序算法大致有以下几种：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序
2、各种排序算法的实现逻辑可简单描述如下：
冒泡排序：不想说了

选择排序：从前往后找到最大的一个与最后一个交换

插入排序：从第二个数开始，认为前面是一个有序数列向前插入

希尔排序： 以n/2为步长分组，插入排序

归并排序 ： 二分法递归，合并两个有序数组

快速排序 ： 第一个为中间值，从右往左找最比中间值小的放左边，从左往右找比中间值大的放右边，左右交叉时第一个放交叉处，递归交叉处左边，递归交叉处右边

堆排序 ： 递归左比较父子大小并交换， 递归右比较父子大小并交换，重建左堆，重建右侧堆

桶排序 ：数据分块儿，常用于大数据。

3、上代码：

//插入排序
void insertFun(int A[], int n)
{
    for (int i=1; i<n; i++) {
        int k=i;
        while (k>=1&&A[k]<A[k-1]) {
            swap(&A[k],&A[k-1]);
            k--;
        }
    }
}
//归并排序
void merge(int *a,int n,int begin,int end)
{
    if (end-begin<=1) {
        return;
    }
    
    merge(a,n,begin,begin+(end-begin+1)/2);
    merge(a,n,begin+(end-begin+1)/2+1,end);
    hebing(a,n,begin+(end-begin+1)/2+1,end);
}
//冒泡排序
void funPaoCompare(int *a,int n,int begin,int end)
{
    for (int i=begin; i<end+1; i++) {
        for (int j=begin; j<end+1-1-i; j++) {
            count++;
            if (a[j]>a[j+1]) {
                swap(&a[j], &a[j+1]);
            }
        }
    }
}
//选择排序
void selectFun(int A[], int n)
{
    for (int i=0; i<n; i++) {
        int minIndex=i;
        for (int j=i+1; j<n; j++) {
            if (A[minIndex]>A[j]) {
                minIndex = j;
            }
        }
        if (minIndex!=i) {
            swap(&A[minIndex], &A[i]);
        }
    }
}
//希尔排序
void shellFun(int A[], int n)
{
    int w = n;
    while(floor(w/2)>=1)
    {
        w=floor(w/2);
        shellFun_detail(A,n,w);
    }
}
void shellFun_detail(int A[], int n, int s)
{
    for (int i=0; i<n; i+=s) {
        int k=i;
        for (int j=i-s; j>=0; j-=s) {
            if (A[k]<A[j]) {
                swap(&A[k], &A[j]);
                k=j;
            }
            else
            {
                break;
            }
        }
    }
}
//快速排序
void quickPai(int *a,int n,int begin,int end)
{
    if (end-begin<=0) {
        return;
    }
    if (end-begin==1&&a[begin]>a[end]) {
        
        swap(&a[begin], &a[end]);
        return;
    }
    int length = end-begin+1;
    int compare = begin,now = end;
    for (int i=begin;i<begin+length;i++) {
        if (compare<now&&a[compare]>a[now]) {
            swap(&a[compare],&a[now]);
            int temp = compare;
            compare = now;
            now = temp+1;
        }
        
        else if (compare>now&&a[compare]<a[now]) {
            
            swap(&a[compare],&a[now]);
            int temp = compare;
            compare = now;
            now = temp-1;
        }
        
        else if(compare<now)
        {
            now--;
        }
        else if (compare>now)
        {
            now++;
        }
    }
    quickPai(a,n,begin,compare-1);
    quickPai(a,n,compare+1,end);
}
//堆排序
void heap(int A[], int n, int s)
{
    if (left(s)>n&&right(s)>n) {
        return ;
    }
    if (left(s)<=n) {
        heap(A, n, left(s));
    }
    if (right(s)<=n) {
        heap(A, n, right(s));
    }
    int min = s;
    if (A[left(s)-1]<A[min-1]) {
        min =left(s);
    }
    if (A[right(s)-1]<A[min-1]) {
        min =right(s);
    }
    if (min!=s) {
        swap(&A[min-1],&A[s-1]);
        heap(A, n, left(s));
        heap(A, n, right(s));
    }
}
int left(int a)
{
    return 2*a;
}
int right(int a)
{
    return 2*a+1;
}
void swap(int *a, int *b)
{
    *a=*a^*b;
    *b=*b^*a;
    *a=*a^*b;
}
//输出
void fun_out(int A[], int n)
{
   for (int i=0; i<n; i++) {
       
       NSLog(@"%i",A[i]);
   }
}

4、其他相关算法

//合并两个有序数列
void heBing(int a[],int m,int b[],int n,int c[])
{    int i=0,j=0,w=0;    
    while (i<m&&j<n) {        
          if (a[i]<b[j]) {            
              c[w]=a[i];i++;w++;       
           }       
         else       
         {            
              c[w]=b[j];j++;w++;        
         }   
     }    
    while (i<m)
     {        
            c[w]=a[i];i++;w++;    
     }    
     while (j<n) 
     {        
            c[w]=b[j];j++;w++;    
     }
}