一、前言

        排序是每个程序员必学会的算法之一,今天我们就来学习一下十分经典的四大排序:冒泡排序、插入排序、选择排序与快速排序吧

二、四大排序算法性能表

        算法稳定性的简单形式为: 如果,排序前 在之前,排序后 还在之前,则称这种排序算法是稳定的,即保证排序前后两个相等的数的相对位置顺序不变

三、冒泡排序

        冒泡排序可以说是代码写起来最简单的一种排序算法了,新手小白们的排序算法基本上也是冒泡排序.它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

        代码如下:

void bubblesort(int *lst,int lstlen){
    for (int i=0;i<lstlen;i++){
        for (int j=0;j<lstlen;j++){
            if (lst[i]<lst[j]){
                int tmp = lst[i];
                lst[i] = lst[j];
                lst[j] = tmp;
            }
        }
    }
}

        运行效果:

四、插入排序

        插入排序(一般也被称为直接插入排序)也是一种十分常用的排序算法,它的原理类似于打扑克牌。对于少量元素的排序，它是一个有效的算法,它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

        代码如下:

void insertsort(int *lst,int lstlen){
    for (int j=1;j<lstlen;j++){
        int comparison = lst[j];
        int i = j - 1;
        while (i>=0 && lst[i]>comparison){
            lst[i+1] = lst[i];
            i--;
        }
        lst[i+1] = comparison;
    }
}

        运行效果:

五、选择排序

        选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

        代码如下:

void selectsort(int *lst,int lstlen){
    for (int i=0;i<lstlen-1;i++){
        int min = i;
        for (int j=i+1;j<lstlen;j++){
            if (lst[j]<lst[min]){
                min = j;
            }
        }
        if (min!=i){
            int tmp = lst[i];
            lst[i] = lst[min];
            lst[min] = tmp;
        }
    }
}

        运行效果:

六、快速排序 

        快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进。 

        快速排序算法通过多次比较和交换来实现排序，其排序流程如下:

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

        代码如下:

void quicksort(int *lstsort,int L,int R){
    int i = L,j = R;
    if (L>=R)
        return;
    int temp = lstsort[i];
    while (i<j) {
        while (i < j && lstsort[j]>=temp) {
            j--;
        }
        lstsort[i] = lstsort[j];
        while (i < j && lstsort[i]<=temp) {
            i++;
        }
        lstsort[j] = lstsort[i];
    }
    lstsort[i] = temp;
    quicksort(lstsort,L, i-1);
    quicksort(lstsort,j+1, R);
}

        运行效果:

七、结束语

         好啦,今天的四大排序就和大家分享到这里啦,祝大家学习愉快,我们下一期再见!

一键三连可以加快更新速度哦!!! Thanks!!!