基础排序方法总结与C++实现

基础排序方法总结

基础排序方法与思路：

实现的排序方法代码：主要理解 归并排序的递归终止条件 和 快速排序的Partition的思路和终止条件（单纯遍历的话会有很多冗余情况）。

// MethodsOfSort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <string.h>

const int numlength = 15;

class MethodOfSort
{
    friend void printArray(int* arr);
public:   
    
    void Swap(int* arr, int i, int j) {
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // 选择排序
    void SelectionSort(int* arr) {
        for (int i = 0; i < numlength; i++) {
            int min_num = arr[i];
            int min_index = i;
            for (int j = i; j < numlength; j++) {
                if (arr[j] < min_num) {
                    min_num = arr[j];
                    min_index = j;
                }
            }
            this->Swap(arr, i, min_index);
        }
    }

    // 冒泡排序
    void BubbleSort(int* arr) {
        int max_num = arr[0];
        int max_index = 0;
        for (int i = 0; i < numlength; i++) {
            max_num = arr[0];
            max_index = 0;
            for (int j = 0; j < numlength - i; j++) {
                if (arr[j] > max_num) {
                    max_num = arr[j];
                    max_index = j;
                }
            }
            this->Swap(arr, max_index, numlength -1 - i);
        }
    }

    // 插入排序
    void InsertSort(int* arr) {

        for (int i = 1; i < numlength; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    this->Swap(arr, j, j - 1);
                }
            }            
        }
    }

    // 归并排序
    void MergeSort(int* arr, int L, int R) {
        if (L == R) {
            return;
        }       
        int mid = L + ((R - L) >> 1); //改成 int mid = L + (R - L) >> 1; 不对，这样子的话是先计算L + (R - L) 再左移
        this->MergeSort(arr, L, mid);
        this->MergeSort(arr, mid + 1, R);
        this->Merge(arr, L, mid, R);
    }
    
    void Merge(int* arr, int L, int mid, int R) {
        int len = R - L + 1;
        int* temp = new int[len]; // 在堆区开辟一个临时数组
        int l = L;//左指针
        int r = mid + 1;//右指针
        int i = 0;
        // 左右指针都不越界时
        while (l <= mid && r <= R) {
            temp[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
        }
        // 右指针先越界
        while (l <= mid) {
            temp[i++] = arr[l++];
        }
        // 左指针先越界
        while (r <= R) {
            temp[i++] = arr[r++];
        }
        // 拷贝到arr
        for (int j = 0; j < len; j++) {
            arr[L + j] = temp[j];
        }
        //释放 temp
        delete [] temp;

    }
    // 快速排序
    void QuickSort(int* arr, int L, int R) {
        if (L < R ) {
            int pivot = arr[R];
            int index[2] = {};
            // 将arr分成大于pivot、等于pivot、大于pivot三部分，index是等于部分的左右索引
            this->Partition(index, arr, L, R, pivot);

            std::cout << "L ==" << L << "R ==" << R << std::endl;
            std::cout << "pivot ==" << pivot << std::endl;
            std::cout << index[0] << "  " << index[1] << std::endl;
            for (int i = 0; i < numlength; i++) {
                std::cout << arr[i] << ' ';
            }
            std::cout << ' ' << std::endl;

            this->QuickSort(arr, L, index[0] - 1);
            this->QuickSort(arr, index[1] + 1, R);
        }

    }
    
    void Partition(int* index,int* arr, int L, int R, int pivot) {
        int lessflag, moreflag;
        lessflag = L - 1;
        moreflag = R + 1;
        int i = L;
        while (i < moreflag && i < R) { //要注意 i < moreflag 的条件，否则回出现重复排序的情况
            if (arr[i] < pivot) {
                this->Swap(arr, i++, ++lessflag);
            }
            else if (arr[i] == pivot) {
                i++;
            }
            else if (arr[i] > pivot && i < moreflag) {
                this->Swap(arr, i, --moreflag);
            }
            
        }
        index[0] = lessflag + 1;
        index[1] = moreflag - 1;
    }
};

void printArray(int* arr)
{
    for (int i = 0; i < numlength; i++) {
        std::cout << arr[i] << ' ';
    }
    std::cout << ' ' << std::endl;
}

int main()
{
    
    srand((unsigned int)time(NULL));
    int a[numlength] = {};
    for (int i = 0; i < numlength; i++) {
        a[i] = rand()/100;
    }

    //int a[numlength] = {1,3,3,4,6,1,2,2,8,5,7,5,1,8,6};

    int b[numlength] = {};
    memcpy(b,a, numlength*sizeof(int));

    int c[numlength] = {};
    memcpy(c, a, numlength * sizeof(int));
    
    int d[numlength] = {};
    memcpy(d, a, numlength * sizeof(int));

    int e[numlength] = {};
    memcpy(e, a, numlength * sizeof(int));


    MethodOfSort MS;

    std::cout << "Before SelectionSort:\n";
    printArray(a);
    MS.SelectionSort(a);
    std::cout << "After SelectionSort:\n";
    printArray(a);

    std::cout << "Before BubbleSort:\n";
    printArray(b);
    MS.BubbleSort(b);
    std::cout << "After BubbleSort:\n";
    printArray(b);

    std::cout << "Before InsertSort:\n";
    printArray(c);
    MS.InsertSort(c);
    std::cout << "After InsertSort:\n";
    printArray(c);

    std::cout << "Before MergeSort:\n";
    printArray(d);
    MS.MergeSort(d, 0, numlength - 1);
    std::cout << "After MergeSort:\n";
    printArray(d);


    std::cout << "Before QuickSort:\n";
    printArray(e);
    MS.QuickSort(e, 0, numlength - 1);
    std::cout << "After QuickSort:\n";
    printArray(e);
}