MENU

排序算法

April 4, 2020 • Read: 303 • 算法

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

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

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),是由 约翰·冯·诺伊曼 发明的一种排序算法,该算法充分体现了分治的思想

排序原理

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

GwGnoT.png

GwKU2t.png

GwGAQs.png

图源 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;
}
Archives Tip
QR Code for this page
Tipping QR Code