排序算法

排序是我们在学习编程的过程中经常用的问题，这篇博客会总结一些我比较常用的一些算法，以供复习和回忆。

比较常见的排序大致分为两种，比较型排序和非比较型排序

比较型排序将元素之间两两进行比较，比较耗时间。
非比较型排序将元素进行记录，比较耗空间。

我们通常认为时间比空间重要，故经常使用牺牲空间的方式来减少运行时间

比较型排序

一、插入排序

一个无序数列，从左到右每次取一个数向左依次比较，直至左边有一个数比它小，则插入。

时间复杂度：O(N)~O(N^{2)
空间复杂度：O(1)}

代码部分：

#include <stdio.h>

void InsertSort(int arr[],int n)
{
	for(int i=0;i<n-1;++i){  //第一个已经排好序，没必要再参与计算
        int end=i;    //记录有序序列当前最后元素的下标
        int temp=arr[end+1];    //待插入的元素
        while(end>=0){
            if(arr[end]>temp){    
                arr[end+1]=arr[end];    //比插入的数大就向后移
                end--;
            }
            else
                break;    //比插入的数小，跳出循环
        }
        arr[end+1]=temp;    //放入temp
	}
}
int main() {
    int arr[20],i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    InsertSort(arr,n);
    for(i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

二、冒泡排序

也是我比较喜欢用的一种排序，每次从左到右相邻的元素两两比较，第一个与第二个比较，让大的那个与第三个比较。这样可以使最大的数排在最右边。

时间复杂度：O(N)~O(N^{2)
空间复杂度：O(1)}

代码部分：

#include <stdio.h>

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

int main() {
    int arr[20],i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    BubbleSort(arr,n);
    for(i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

非比较型排序

计数排序（Count sort）

计数排序也就是我们刚接触数组时使用的排序方法，快于任何一种比较型排序算法，但条件较为苛刻：数据范围较小，否则非常浪费空间

k为数组长度
时间复杂度就是O(n+k)
空间复杂度为O(k)

#include <stdio.h>

int main() {
    int arr[1000],brr[1000]={0};
    int n,i,j;
    scanf("%d",&n);
    scanf("%d",&arr[0]);
    brr[arr[0]]++;
    int max=arr[0];
    for(i=1;i<n;i++){
        scanf("%d",&arr[i]);
        brr[arr[i]]++;
        if(arr[i]>max)
            max=arr[i];
    }
    for(i=0;i<max+1;i++){
        for(j=0;j<brr[i];j++){
            printf("%d ",i);
        }
    }
    return 0;
}