【算法】九大排序算法总结

悠悠 2022-08-05 07:50 225阅读 0赞

# 数据结构 #

这里我不采用数组来进行排序，而是采用更加符合应用的数据结构来排序。

#define M 100
    typedef int datatype;
    typedef struct node{
        datatype r[M+1];
        int lengh;
    }table;

这是一种简单描述，更加详细的数据机构应该是下面这样（但是为了方便描述还是使用上面的简单结构）：

#define M 100
    typedef int datatype;
    typedef struct {
        datatype key;
        //其他数据...
    }sort_record;
    typedef struct node{
        sort_record r[M+1];
        int lengh;
    }table;

**说明：这里不考虑程序的鲁棒性，对于略去了对参数的检查，只为了更加清晰地描述算法，本来想用数组的但是觉得使用结构体更加合乎实际应用逻辑。每种算法都是必须非常熟练的，至于思路就不用说了读代码就行**  
注意：数组中第一个元素tab\[0\]都是拿来作为哨兵元素的。默认升序排序。

# 插入排序 #

## 1. 直接插入排序 ##

//1.直接插入
    void direct_insert_sort(table* tab)
    {
        int i,j;
        for (i = 1;i<tab->lengh;i++)
        {
            j = i-1;
            tab->r[0] = tab->r[i];
            while(tab->r[0] < tab->r[j])
            {
                tab->r[j+1] = tab->r[j];
                j = j-1;
            }
            tab->r[j+1] = tab->r[0];
        }
    }

## 2. 二分插入排序 ##

当某些元素是有序的时候，利用二分查找，找到插入的位置，然后插入位置后面的元素后移一位。

void binary_insert_sort(table* tab)
    {
        int i,j,left,right,mid;
        for(i =1;i<tab->lengh;i++)
        {
            left = 1;right = i-1;
            tab->r[0] = tab->r[i];
            while(left <= right)
            {
                mid = (left + right) /2;
                if (tab->r[mid] > tab->r[0]){
                    right = mid -1;
                }
                else{
                    left = mid+1;
                }
            }
            for (j=i-1;j>=left;j--)
            {
                tab->r[j+1] = tab->r[j];
            }
            tab->r[left] = tab->r[0];
        }
    }

## 3. 希尔插入排序 ##

void shell_sort(table* tab)
    {
        int i,j,gap;
        gap = tab->lengh / 2;
        while(gap >= 1)
        {
            for (i = 1+gap;i<=tab->lengh;i++)
            {
                j = i -gap;
                tab->r[0] = tab->r[i];
                while(tab->r[0] < tab->r[j] && j>0)
                {
                    tab->r[j+gap] = tab->r[j];
                    j = j-gap;
                }
                tab->r[j +gap] = tab->r[0];
            }
            gap = gap/2;
        }
    }

# 交换排序 #

## 4. 冒泡排序 ##

//4.冒泡排序
    void bubble_sort(table* tab)
    {
        int i,j,done;
        done = 1;
        for(i = 1;i<= tab->lengh&&done;i++)
        {
            done = 0;
            for (j = 1;j<= tab->lengh - i;j++)
            {
                if (tab->r[j] > tab->r[j+1])
                {
                    swap(tab->r[j],tab->r[j+1]);
                    done = 1;
                }
            }
        }
    }

## 5. 快速排序 ##

//5.快速排序
    void quick_sort(table* tab,int left,int right)
    {
        if (left >= right)
            return;
        int i,j;
        i = left;j = right;
        tab->r[0] = tab->r[i];
        while(i < j)
        {
            while(tab->r[i] <= tab->r[j]&&i<j)
                j--;
            if (i<j){
            tab->r[i] = tab->r[j];
                i++;
            }
            while(tab->r[j] >= tab->r[i]&&i<j)
                i++;
            if (i<j){
                tab->r[j] = tab->r[i];
                j--;
            }
        }
        tab->r[i] = tab->r[0];
        quick_sort(tab,left,i-1);
        quick_sort(tab,i+1,right);
    }

# 选择排序 #

## 6. 直接选择排序 ##

//6.直接选择
    void direct_select_sort(table* tab)
    {
        int i,j,k;
        for (i =1;i<=tab->lengh;i++)
        {
            k = i;
            for(j = i+1;j<=tab->lengh;j++)
            {
                if (tab->r[k] > tab->r[j])
                    k = j;
            }
            if (k != i)
            {
                swap(tab->r[k],tab->r[i]);
            }
        }
    }

## 7. 堆排序 ##

//7.堆排序
    //index表示要调整的节点的下标，n表示堆元素个数。
    void shift_heap(table* tab,int index,int n)
    {
        int i,j,finished = 0;
        tab->r[0] = tab->r[index];
        i = index; j = 2*i;
        while(j<=n && !finished)
        {
            if (tab->r[j] > tab->r[j+1]&&j<=n)
                j++;
            if (tab->r[0] <= tab->r[j])
            {
                finished = 1;
            }
            else
            {
                tab->r[i] = tab->r[j];
                i = j;
                j = 2*i;
            }
        }
        tab->r[i] = tab->r[0];
    }
    void heap_sort(table* tab)
    {
        int i;
        for (i = tab->lengh/2;i>=1;i--)
        {
            shift_heap(tab,i,tab->lengh);
        }
        for (int i = 2;i<tab->lengh;i++)
        {
            shift_heap(tab,i,tab->lengh);
        }
    }

# 8. 归并排序 #

//8.归并排序
    //将tabs中的u-m-v的元素合并到tabg中
    void merge(table* tabs,table* tabg,int u,int m,int v)
    {
        int i,j,k,t;
        i = u; j = m +1;
        k = u;
        while(i<=m && j <= v)
        {
            if (tabs->r[i] < tabs->r[j])
            {
                tabg->r[k++] = tabs->r[i];
                i++;
            }
            else
            {
                tabg->r[k++] = tabs->r[j];
                j++;
            }
        }
        if (i<=m)
        {
            for(t = i;t<=m;t++)
                tabg->r[k++] = tabs->r[t];
        }
        else
        {
            for(t = i;t<=v;t++)
                tabg->r[k++] = tabs->r[t];
        }
    }
    //递归实现
    void merge_sort1(table* tabs,table* tabg,int left,int right)
    {
        if (left>= right)
        {
            return;
        }
        int mid = (left+right)/2;
        merge_sort1(tabs,tabg,left,mid);
        merge_sort1(tabs,tabg,mid+1,right);
        merge(tabs,tabg,left,mid,right);
    }
    //非递归实现
    void merge_pass(table* tabs,table* tabg,int len)
    {
        int i,j,n;
        tabg->lengh = n = tabs->lengh;
        for(i =1;i<n-2*len+1;i+=2*len)
        {
            merge(tabs,tabg,i,i+len-1,i+2*len-1);
        }
    
        if (i+len-1<n){
            merge(tabs,tabg,i,i+len-1,n);
        }
        else{
            for(j=i;j<=n;j++){
                tabg->r[j] = tabs->r[j];
            }
        }
    }
    void merge_sort(table* tab)
    {
        int len;
        table tmp;
        len =1;
        while(len<tab->lengh)
        {
            merge_pass(tab,&tmp,len);
            len = 2*len;
            merge_pass(&tmp,tab,len);
            len = 2*len;
        }
    }

# 9. 桶排序 #

桶排序(Bucket Sort)的原理很简单，它是将数组分到有限数量的桶子里。  
假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围\[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个”桶”。  
在排序时，逐个遍历数组a，将数组a的值，作为”桶数组r”的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a\[3\]=5，则将r\[5\]的值+1。

桶排序不能应用于排序数很大的情况，因为这样会需要一个很大很大桶，显然是科学的。  
桶排序是**稳定**的，最好的时间复杂度达到O(N)

/*
    * 桶排序
    *  tab -- 排序结构
    *  max --待排序结构中最大范围[0,max)
    */
    void bucket_sort(table* tab,int max)
    {
        int i,j;
        int* bucket;
        if (tab == NULL || tab->lengh > max || max < 1)
            return;
        if ((bucket = (int*)malloc(sizeof(int)*max)) == NULL)
            return;
        memset(bucket,0,max*sizeof(int));
        //1.计数
        for (i = 1;i<tab->lengh;i++)
        {
            bucket[tab->r[i]]++;
        }
        //2.排序
        for(i = 1,j = 1;i < max;i++)
        {
            while(bucket[i]-- != 0)
                tab->r[j++] = i;
        }
        free(bucket);
    }

# 基数排序 #

基数排序比较麻烦，自我认为找工作，面试笔试都不会考到，理解基本思路即可。  
实现思路：

> 最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。  
> 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。