排序算法

Program sort

创建时间:2020-03-16 15:37

阅读:

快排
归并
冒泡

常用的排序算法:冒泡,归并,快排

快排

快速排序采用分治策略:找到一个轴点,比它小的放在左侧,大的放在右侧,不断划分

最坏情况O(n^2),大多数情况下平均效率O(nlogn),常系数比其它的小,实际的平均运行时间比同类的更少.
但是快速排序无法保证数据之间的相对次序(主要针对重复元素)

#include <cstdlib>
#include <iostream>
using namespace std;

// [lo hi) sort
template <typename T>
int partition(T arr[], int lo, int hi){
    int index = lo + rand()%(hi-lo);
//    swap arr[lo] and arr[index]
    T mi = arr[index];
    arr[index] = arr[lo];
    arr[lo] = mi;
    hi--;  // point to last data
    // < 勤于交换 相对于<=更好,能较为均衡划分 
    while(lo < hi){
        while(lo < hi){
            if(mi < arr[hi]){ hi--; }
            else{arr[lo++] = arr[hi]; break;}
        }
        while(lo < hi){
            if(arr[lo] < mi){lo++; }
            else{arr[hi--] = arr[lo]; break;}
        }
    }
    arr[lo] = mi;
    return lo;
}

template <typename T>
void quicksort(T arr[], int length, int lo, int hi){
//    judge the input
    if(hi < lo || hi - lo > length|| arr == NULL){
        cout << "invalid input";
        exit(1);
    }
    if(hi-lo < 2)
        return;
//    partition and sort
    int middle = partition(arr, lo, hi);
    quicksort(arr, length, lo, middle);
    quicksort(arr, length, middle+1, hi);
}

// override
template <typename T>
void quicksort(T arr[], int length){
    quicksort(arr, length, 0, length);
}

归并

从中间分成两部分,然后分别排序,最后归并
每一层递归消耗时间稳定在$\Theta(n)$,共有$\Theta\left(\log _{2} n\right)$层,共计$\Theta(\text {n} 1 \text {ogn})$

template <typename T>
void merge(T arr[], int lo, int middle, int hi){
    int len_l = middle - lo;
    int len_r = hi - middle;
    T *temp_left = new T[len_l];
    for(int i=0;i<len_l;i++){temp_left[i] = arr[lo+i]; }
    T *temp_right = arr + middle;
    T *glo_arr = arr + lo;
    for(int i=0,j=0,k=0;j< len_l || k < len_r;){
        if(j < len_l && (temp_left[j] <= temp_right[k] || k == len_r)){glo_arr[i++] = temp_left[j++];}
        if(k < len_r && (temp_right[k] < temp_left[j] || j == len_l)){glo_arr[i++] = temp_right[k++];}
    }
    delete [] temp_left;
}

template <typename T>
void mergesort(T arr[], int length, int lo, int hi){
//    judge the input
    if(hi-lo > length || hi<lo){
        cout<< "invalid input";
        exit(1);
    }
    if(hi - lo < 2)
        return;
    int middle = (lo + hi)>>1;
    mergesort(arr, length, lo, middle);
    mergesort(arr, length, middle, hi);
    merge(arr, lo, middle, hi);
}

template <typename T>
void mergesort(T arr[], int length){
    mergesort(arr, length, 0, length);
}

冒泡

复杂度O(n^2)

template <typename T>
void bubblesort(T arr[], int length){
    for(int i=0;i<length-1;i++){
        for(int j=0;j<length-1-i;j++){
            if(arr[j] > arr[j+1]){
                T temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 yangbenbo@whu.edu.cn