排序算法

排序算法(选择排序、冒泡排序、插入排序、归并排序)

排序算法是计算机科学领域中被广泛研究的一个课题，历时多年，它发展出了数十种算法，这些算法都着眼于一个问题： 如何将一个无序数组整理成升序？
接下来，我讲介绍其中的四种常用的排序算法：冒泡排序，选择排序，插入排序，归并

1.冒泡排序

冒泡排序通过不停的比较前后两个元素的大小，并将其排序，从而最终使大的元素排到数组末尾，从而达到排序的目的。

代码如下：

#include <stdio.h>

int main() {
    int list[20]={2,5,4,1,6,3,7,9,8};
    int flag=1,unsorted_index=9-1;
    while (flag){
        flag=0;
        for (int i=0;i<unsorted_index;i++){
            if (list[i]>list[i+1]){
                flag=1;
                int temp=list[i];
                list[i]=list[i+1];
                list[i+1]=temp;
            }
        }
        unsorted_index--;
    }
    for (int i=0;i<9;i++){
        printf("%d ",list[i]);
    }
    return 0;
}

2.选择排序

选择排序通过不停的寻找起始数后的最小值，并将最小值与起始位置进行交换，经过不停的处理以后，可以得到升序的数组。

代码如下：

#include <stdio.h>
//选择排序
int main() {
    int list[20]={9,5,1,3,4,5,6,7,2};
    int min;
    for (int i=0;i<9;i++){
        min=i;
        for (int j=i+1;j<9;j++){
            if (list[j]<list[min]){
                min=j;
            }
        }
        if (min!=i){
            int temp=list[min];
            list[min]=list[i];
            list[i]=temp;
        }
    }
    for (int i=0;i<9;i++){
        printf("%d ",list[i]);
    }
    return 0;
}

3.插入排序

插入排序通过将起始位置的元素与起始元素前的元素进行比较，如果小于该元素并且大于前一个元素，那么，将该起始元素插入两元素之间

代码如下：

#include <stdio.h>
//插入排序
int main() {
    int list[20]={3,4,6,5,2,7,1,8};
    int position,value;
    for (int i=1;i<8;i++){
        position=i;
        value=list[i];
        //注意，此处必须要使用value来代表i处的值
        //否则随着数组的变化，原本的list[i]会不停的发生变化
        //导致排序结果错误
        while (position>0&&list[position-1]>value){
            list[position]=list[position-1];
            position--;
        }
        list[position]=value;
    }
    for (int i=0;i<8;i++){
        printf("%d ",list[i]);
    }
    return 0;
}

结语

在最糟糕的条件下，选择排序是最优的排序方式，而插入排序是最糟糕的排序方式，但是在一般条件下，如果你确信数组大致是有序的，那么插入排序会更好，如果是比较混乱的情况，则选择排序比较好，如果无法确定的话，两种都可以。

4.归并排序（2020.2.6更新）

归并排序是排序算法中的一种比较稳定的算法，他的时间复杂度为 O(n log n)，是由 约翰·冯·诺伊曼 发明的一种排序算法，该算法充分体现了分治的思想

排序原理

这里用几张图片来解释归并排序

图源 https://www.cnblogs.com/chengxiao/p/6194356.html

C++代码

#include <bits/stdc++.h>
using namespace std;
int data[100]={1,9,6,7,5,3,2,6},result[100];
void merge(int start,int end){
    //这里对应的是治，将分好的数据进行排序
    int left_length=(end-start+1)/2;
    int left_index=start;
    int right_index=start+left_length;
    int result_index=start;
    //将数据从中间分成两半
    //以下过程对应第三张图，借用额外开出的数组进行排序
    while (left_index<start+left_length && right_index<end+1){
        if (data[left_index]<=data[right_index])
            result[result_index++]=data[left_index++];
        else
            result[result_index++]=data[right_index++];
    }
    //将剩下的数据一次放到新开出的数组里面
    while (left_index<start+left_length)
        result[result_index++]=data[left_index++];
    while (right_index<end+1)
        result[result_index++]=data[right_index++];
}
void merge_sort(int start,int end){
    //这里对应的是分，利用递归，不停的将数据分成两半
    if (1==end-start){
    //当只有两个数据的时候，排序
        if (data[start]>data[end]){
            int tmp=data[start];
            data[start]=data[end];
            data[end]=tmp;
        }
        return ;
    }
    else if (end==start){ //如果只有一个数字，则不用排序
        return ;
    }else{
        //递归，循环调用
        merge_sort(start,(end-start+1)/2+start-1);
        merge_sort((end-start+1)/2+start,end);
        merge(start,end); //治
        for (int i=start;i<=end;i++)
            data[i]=result[i];
        //将排好的队重新放回原数组
    }
}
int main() {
    int length=8;
    //待排序数组元素个数
    merge_sort(0,length-1);
    for (int i=0;i<length;i++)
        cout<<data[i]<<" ";
    cout<<endl;
    return 0;
}