B站-8.十种排序

快速排序

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
快速排序实现
*/
int FindPos(int * a, int low, int high);
void QuickSort(int * a, int low, int high);

int main(void)
{
    int a[6] = {-2, 1, 0, -985, 4, -93};
    int i;

    QuickSort(a, 0, 5); //第二个参数表示第一个元素的下标  第三个参数表示最后一个元素的下标

    for (i=0; i<6; ++i)
        printf("%d  ", a[i]);
    printf("\n");

    return 0;
}

void QuickSort(int * a, int low, int high)
{
    int pos;

    if (low < high)
    {
        pos = FindPos(a, low, high);
        QuickSort(a, low, pos-1);
        QuickSort(a, pos+1, high);
    }
}

int FindPos(int * a, int low, int high)
{
    int val = a[low];

    while (low < high)
    {
        while (low<high  && a[high]>=val)
            --high;
        a[low] = a[high];

        while (low<high && a[low]<=val)
            ++low;
        a[high] = a[low];
    }//终止while循环之后low和high一定是相等的

    a[low] = val;

    return high; //high可以改为low, 但不能改为val 也不能改为a[low]  也不能改为a[high]
}

```

冒泡排序

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
冒泡排序实现
*/
int main()
{
    int i=0,j=0,len=0,t=0;
    int a[5]={1,10,50,30,61};
    len=sizeof(a)/ sizeof(a[0]);
    for(i=0;i<len-1;i++){
        for(j=0;j<len-1-i;j++){
            if(a[j]>a[j+1]){
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
    printf("冒泡排序后的数据为：");
    for(i=0;i<len;i++){
        printf("%d ",a[i]);
    }

}
```

插入排序

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
插入排序实现
*/
void InsertionSort(int *num,int n);
int main()
{
    int i=0,len=0;
    int a[5]= {1,10,50,30,61};
    len=sizeof(a)/ sizeof(a[0]);
    InsertionSort(a,len);
    printf("插入排序后的数据为：");
    for(i=0; i<len; i++)
    {
        printf("%d ",a[i]);
    }

}
void InsertionSort(int *num,int n)
{
    int i = 0;
    int j = 0;
    int tmp = 0;
    for(i = 1; i<n; i++)
    {
        tmp = num[i];//从待插入组取出第一个元素。
        j = i-1; //i-1即为有序组最后一个元素（与待插入元素相邻）的下标
        while(j>=0&&tmp<num[j])  //注意判断条件为两个，j>=0对其进行边界限制。第二个为插入判断条件
        {
            num[j+1] = num[j];//若不是合适位置，有序组元素向后移动
            j--;
        }
        num[j+1] = tmp;//找到合适位置，将元素插入。
    }
}
```

选择排序

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
选择排序实现
*/
int main()
{
    int a[6] = {-2, 1, 0, -985, 4, -93};
    int len=sizeof(a)/ sizeof(a[0]);
    for(int i=0;i<len;i++){
        int min = i;//最小元素的下标
        for(int j=i+1;j<len;j++){
            if(a[j]<a[min]){
                min = j;
            }
        }
        int temp = a[i];
        a[i]=a[min];
        a[min] = temp;

    }
    printf("选择排序后的数据为：");
    for(int i=0;i<len;i++){
        printf("%d ",a[i]);
    }
}
```

归并排序

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
#define Max_ 10
// 打印结果
void Show(int  arr[], int n)
{
    int i;
    for ( i=0; i<n; i++ )
        printf("%d  ", arr[i]);
    printf("\n");
}

// 归并排序中的合并算法
void Merge(int array[], int left, int m, int right)
{
    int aux[Max_] = {0};  // 临时数组 （若不使用临时数组，将两个有序数组合并为一个有序数组比较麻烦）
    int i; //第一个数组索引
    int j; //第二个数组索引
    int k; //临时数组索引

    for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分别将 i, j, k 指向各自数组的首部。
    {
        //若 i 到达第一个数组的尾部，将第二个数组余下元素复制到 临时数组中
        if (i == m+1)
        {
            aux[k] = array[j++];
            continue;
        }
        //若 j 到达第二个数组的尾部，将第一个数组余下元素复制到 临时数组中
        if (j == right+1)
        {
            aux[k] = array[i++];
            continue;
        }
        //如果第一个数组的当前元素 比 第二个数组的当前元素小，将 第一个数组的当前元素复制到 临时数组中
        if (array[i] < array[j])
        {
            aux[k] = array[i++];
        }
        //如果第二个数组的当前元素 比 第一个数组的当前元素小，将 第二个数组的当前元素复制到 临时数组中
        else
        {
            aux[k] = array[j++];
        }
    }

    //将有序的临时数组 元素 刷回 被排序的数组 array 中，
    //i = left , 被排序的数组array 的起始位置
    //j = 0， 临时数组的起始位置
    for (i = left, j = 0; i <= right; i++, j++)
    {
        array[i] = aux[j];
    }
}

// 归并排序
void MergeSort(int array[], int start, int end)
{
    if (start < end)
    {
        int i;
        i = (end + start) / 2;
        // 对前半部分进行排序
        MergeSort(array, start, i);
        // 对后半部分进行排序
        MergeSort(array, i + 1, end);
        // 合并前后两部分
        Merge(array, start, i, end);
    }
}

int main()
{   //测试数据
    int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
    //排序前数组序列
    Show( arr_test, Max_ );
    MergeSort( arr_test, 0, Max_-1 );
    //排序后数组序列
    Show( arr_test, Max_ );
    return 0;
}
```

希尔排序

```
void ShellSort(SqList *L)//下标0不存储元素，暂时存储元素使用
{
    int i,j;
    int increment=L->length;//增量值
    do
    {
        increment=increment/3+1;
        /*增量序列*/
        for( i=increment+1; i<=L->length; i++ )
        {
            if (L->r[i]<L->r[i-increment])
            {
                /*需将L->r[i]插入有序增量子表*/
                L->r[0]=L->r[i];/*暂存在L->r[0] */
                for (j=i-increment; j>0&&L->r[0]<L->r[j]; j-=increment)
                    {
                        L->r[j+increment]=L->r[j];/*记录后移，查找插入位置*/
                    }
                L->r[j+increment]=L->r[0]; /*插入*/
            }
        }
    }
    while (increment>1);
}
```

堆排序

```
package sortdemo;

import java.util.Arrays;

/**
 * 堆排序demo
 */
public class HeapSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
```