排序

排序

排序算法的分类

注释：所有的均以从小到大开始排序

插入类

直接插入排序

算法思想：这很类似于玩扑克牌时，去整理牌的操作。将牌分为两个区域，一个已排序的区域（可以为0），一个待排序区域；

将待排序区域的牌，依次与已排序区域的去比较，然后插入到相应的位置即可。\

void InsertSort(int arr[],int len){
    int temp;   //定义变量temp
    for(int i=1;i<len;i++){
        temp = arr[i];  //记录待排序区域的第一个元素
        j = i-1;   //记录已排序区域的最后一个元素
        while(j>=0 && temp<arr[j]){ //j > 0表示已排序区域遍历未完成
            arr[j+1] = arr[j]; // 向后移动元素。（仅个人这么理解：将此时的第i个元素划入已排序字段，进行排序，此时的数组中的第i个元素存放在temp中）
            --j;
        }
        arr[j+1] = temp;
    }
}

折半插入排序

希尔排序

算法思想：将待排序序列按照某种规则划分为几个子序列，分别对这几个子序列进行直接插入排序。

交换类排序

冒泡排序

算法思想：将数组中的相邻的书比较，如果关键字1>关键字2，则交换（如果小于则不交换）；若关键字2>关键字3,则继续交换（如果小于则不交换）

void BubbleSort(int arr[],int n){
    int temp;
    for(int i = n-1;i>=1;--i){
        for(int j = 1;j <=i;j++){
            if(arr[j-1]>arr[j]){
                temp = arr[j-1];
                arr[j-1]=arr[j];
                arr[j] = temp;
            }
        }
    }
}

时间复杂度：O(n*n)

快速排序

算法思想：每一躺选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移动到枢轴前面，比枢轴大的移动到枢轴后面，当本躺所有子序列都被枢轴按照以上规则划分完成后得到新的一组更短的子序列，它们成为下一趟划分的初始序列集。

int QuickSort(int arr[],int low,int high){
    int t;//临时变量
    int i=low,j=high;
    if(low < high){
        t = arr[low];
    
        while(i<j){
            while(j > i && arr[j] >= t){ //寻找小于 t 的关键字
                --j;
            }
            if(i < j){
                arr[i] = arr[j];
                ++i;
            }
            while( i < j && arr[i] < t){
                ++i;
            }
            if(i < j){
                arr[j] = arr[i];
                --j;
            }
        }
        arr[i] = t;
        QuickSort(arr,low,i-1);
        QuickSort(arr,i+1,high);
    }
}

时间复杂度：(nlogn)

选择类排序

简单选择排序

算法思想：

int SelectSort(int arr[],int len){
    int min;//记录最小值
    int t;
    for(int i=0;i<len;i++){
        min = i;
        for(int j=i+1;j<len;j++){
            if(arr[min] > arr[j]){
                min=j;
            }
        }
        t=arr[i];
        arr[i]=arr[min];
        arr[min]= t;
    }
}

堆排序

满足任意一个非叶结点的值都不大于（或者不小于）其左、右孩子结点的值。若父亲大孩子小，则是大顶堆，若父亲小小孩大，则叫做小顶堆。

归并排序

二路归并排序

基数类排序