MrXiao

[排序算法]冒泡排序 快速排序入门及简单优化
作为志向在科班的有志青年,不能只浮于表面看工程,也得放下身段学基础算法。与年少时就开始沉迷于NOIP的少年们相比,...
扫描右侧二维码阅读全文
25
2019/02

[排序算法]冒泡排序 快速排序入门及简单优化

作为志向在科班的有志青年,不能只浮于表面看工程,也得放下身段学基础算法。与年少时就开始沉迷于NOIP的少年们相比,我还得从十分基本的排序算法学起。不过为了给以后的学习铺平道路,辛苦一点学习也在所难免吧!

冒泡排序

作为C课堂上第一个接触到的排序算法,冒泡排序属于比较式排序中最基础的。原理是相邻两个数比较,大的元素后移;经过第一轮排序之后最大的元素位于数组末尾,第二大的元素位于倒数第二位;循环依次进行即可,时间复杂度为$ O(n^2) $。
基本实现(C):

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

改进1

如果某一轮两两比较中没有任何元素交换,这说明已经都排好序了,算法结束,可以使用一个Flag做标记,默认为0,如果发生交互则置为对应位置,每轮结束时检测Flag,如果为非0则继续,如果为0则返回。

void BubbleSort(int arr[],int size){
    int lastSwap;
    for (int i = 0; i < size-1; ++i) {
        lastSwap = 0;
        for (int j = size-1; j > i; --j) {
            if (arr[j-1]>arr[j]){
                int t=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=t;
                lastSwap = j;
            }
        }
        if(!lastSwap)
            break;
    }
}

改进2

某一轮结束位置为j,但是这一轮的最后一次交换发生在lastSwap的位置,则lastSwap到j之间是排好序的,下一轮的结束点就不必是j--了,而直接到lastSwap即可,代码如下:

void bubble_sort (int a[], int n) {
    int i, j, lastSwap, tmp;
    for (j=n-1; j>0; j=lastSwap) {
        lastSwap=0;     //每一轮要初始化为0,防止某一轮未发生交换,lastSwap保留上一轮的值进入死循环
        for (i=0; i<j; i++) {
            if (a[i] > a[i+1]) {
                tmp=a[i];
                a[i]=a[i+1];
                a[i+1]=tmp;
           //最后一次交换位置的坐标
                lastSwap = i;
            }
        }
    }
}

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。快速排序采用分治法策略将一个序列分为两个。

具体步骤:

  • 从数列中挑出一个元素称为基准(pivot),通常以第一个元素为基准。
  • 所有小于基准数的元素放在基准数之前,同理大于基准数的元素放在基准数之后。具体的实现方法如图所示:
void quicksort(int arr[],int left,int right){
    int i,j,t,temp;
    if(left>right)
        return;
    temp=arr[left];
    i=left;
    j=right;
    while(i!=j){
        while(arr[j]>=temp and i<j)
            j--;
        while(arr[i]<=temp and i<j)
            i++;
        if(i<j){
            t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }
    }
    arr[left]=arr[i];
    arr[i]=temp;
    quicksort(arr,left,i-1);
    quicksort(arr,i+1,right);
}
Last modification:February 26th, 2019 at 03:17 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment