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

自建测试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);
            }
        }
    }
}

测试程序

int main() {
    vector<int> arr(10000);
    int arr1[10000];
    int arr2[10000];
    int arr3[10000];
    commonsort s;
    for (int i = 0; i < 10000; ++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, 10000 - 1);
    clock_t time3 = clock();
    s.MergeSort(arr2, 10000);
    clock_t time4 = clock();
    s.BubbleSort(arr3, 10000);
    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版本测得数据

STL自带sort消耗时间：0ms
快速排序消耗时间：1ms
归并排序消耗时间：1ms
冒泡排序消耗时间：102ms

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

原文：https://www.cnblogs.com/Joy2013Ru/p/13704690.html