时间戳

首页 > 技术文章 > 几种常用的高效排序算法学习（待续）

几种常用的高效排序算法学习（待续）

Joy2013Ru 2020-09-21 11:47 原文

目录

自建测试class

class commonsort {
public:
    void QuickSort(int arr[], int left, int right); //传入数组和排序区间[left,right]
    bool MergeSort(int arr[], int len); //传入数组和数组长度
    void BubbleSort(int arr[],int len);//传入数组和数组长度
private:
    static int Mypartition(int arr[], int left, int right);
    static void mergesort(int arr[], int first, int last, int temp[]);
    static void mergearray(int arr[], int first, int mid, int last, int temp[]);
private:
    static void swap(int arr[],int len,int a, int b);
};

快速排序

  • 基本思想
  1. 先从数组中取出一个数作为基准数
  2. 区分过程，将比这个数大的数放到它的右边，小于或等于它的数放到左边
  3. 再对左右区间重复第二步，直到各个区间都只有一个数

code

void commonsort::QuickSort(int arr[], int left, int right) {
    int pivot = 0;
    if (left < right) {
        pivot = Mypartition(arr, left, right);
        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int commonsort::Mypartition(int arr[], int left, int right) {
    int key = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= key) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= key) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = key;
    return left;
}

归并排序

  • 基本思想
  1. 把目标数组分成两组，判断这两组数据是否有序
  2. 如果不是有序的数组，可以再分，直至有序或者那个小组只剩一个数据
  3. 借助额外申请的空间，比较合并两个相邻的小组

code

bool commonsort::MergeSort(int arr[], int len) {
    int* temp = new int[len];
    if (temp == NULL)
        return false;
    mergesort(arr, 0, len - 1, temp);
    delete[] temp;
    return true;
}

void commonsort::mergesort(int arr[], int first, int last, int temp[]) {
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(arr, first, mid, temp);    //左边有序
        mergesort(arr, mid + 1, last, temp); //右边有序
        mergearray(arr, first, mid, last, temp); //再将二个有序数列合并
    }
}

void commonsort::mergearray(int arr[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    while (i <= m)
        temp[k++] = arr[i++];

    while (j <= n)
        temp[k++] = arr[j++];

    for (i = 0; i < k; i++)
        arr[first + i] = temp[i];
}

冒泡排序（对比测试用）

  • 基本思想
  1. 不断遍历整个数组，两两比较，小的交换到大的左边,直至所有数都符合左边小右边大
  2. 最好情况是遍历1次
  3. 最坏情况是遍历n次
void commonsort::swap(int arr[],int len,int a, int b) {
    if (arr == nullptr) return;
    if (a < 0) return;
    
    int temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void commonsort::BubbleSort(int arr[],int len) {
    if (arr == nullptr) return;
    for (int i = 0; i < len - 1; ++i) {
        for (int j = 0; j < len - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, len, j, j + 1);
            }
        }
    }
}

测试程序

vector<int> arr(500000);
int arr1[500000];
int arr2[500000];
int arr3[500000];
//放那么多个元素就需要用全局变量了，局部变量会爆栈
int main() {
    commonsort s;
    for (int i = 0; i < 500000; ++i) {
        arr[i] = rand() % 1000;
        arr1[i] = rand() % 1000;
        arr2[i] = rand() % 1000;
        arr3[i] = rand() % 1000;
    }
    clock_t time1 = clock();
    sort(arr.begin(), arr.end());
    clock_t time2 = clock();
    s.QuickSort(arr1, 0, 500000 - 1);
    clock_t time3 = clock();
    s.MergeSort(arr2, 500000);
    clock_t time4 = clock();
    s.BubbleSort(arr3, 500000);
    clock_t time5 = clock();
    cout << "STL自带sort消耗时间：" << time2 - time1 << "ms" << endl;
    cout << "快速排序消耗时间：" << time3 - time2 << "ms" << endl;
    cout << "归并排序消耗时间：" << time4 - time3 << "ms" << endl;
    cout << "冒泡排序消耗时间：" << time5 - time4 << "ms" << endl;
    return 0;
}

在vs下Release版本测得数据（分别用50w个随机数测试）

STL自带sort消耗时间：18ms
快速排序消耗时间：74ms
归并排序消耗时间：48ms
冒泡排序消耗时间：320588ms

结论
由于STL自带的sort是世界级大神们结合快速排序，归并排序，插入排序，堆排序等实现的，所以综合性能很强。
归并比快速效率稍高，冒泡。。。

推荐阅读