首页 > 代码库 > 下午闲来没事儿,把几种常见的排序都码了一遍

下午闲来没事儿,把几种常见的排序都码了一遍

  • Source code

/*

内部排序相关代码总结

*/

#include<windows.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<fstream>

#include<math.h>

#include<time.h>

#define N 10000 //待排序的数据规模

static unsigned int T = 17;

using namespace std;

void SetData(int num)

{

    ofstream write;

    write.open("待排序的测试数据.txt");

    if (!write){

        cout << "error" << endl;

        exit(1);

    }

    for (int i = 1; i <= num; ++i)

    {

        srand((int)time(0) * ((T += 7)));

        write << rand() % 100007;

        if (i < num){

            write << endl;

        }

    }

    write.close();

}

void GetData(vector<int>& data)

{

    ifstream read;

    read.open("待排序的测试数据.txt");

    if (!read){

        cout << "error" << endl;

        exit(1);

    }

    while (!read.eof())

    {

        int tem;

        read >> tem;

        data.push_back(tem);

    }

    read.close();

}

void SetOrderData(vector<int> data)

{

    ofstream write;

    write.open("排序后数据.txt");

    for (unsigned int i = 0; i < data.size(); ++i)

    {

        write << data[i] << endl;

    }

    write.close();

}

   

/*    

    直接插入排序

*/

void StraightInsertSort(vector<int>& data)

{

    int tem = 0; //代替 0 单元的作用

    if (data.size() <= 1){

   

    }

    else{

        for (unsigned int i = 1; i < data.size(); ++i)

        {

            if (data[i] < data[i - 1]){

                tem = data[i];

                data[i] = data[i - 1]; //记录后移

                int j; //第一趟插入 j 会等于 -1

                for (j = i - 1; (j >= 0) && (tem < data[j]); --j){

                    data[j + 1] = data[j];//记录后移

                }

                data[j + 1] = tem;//插入正确位置

            }

        }

    }

}

   

/*

    折半插入排序

*/

void BinaryStraightInsertSort(vector<int>& data)

{

    int tem = 0;

    if (data.size() <= 1){

   

    }

    else{

        for (int i = 1; i < data.size(); ++i)

        {

            tem = data[i];

            int low = 0, high = i - 1;

   

            while (low <= high)

            {

                int mid = (low + high) / 2;

                if (tem < data[mid]){

                    high = mid - 1;//插入点在低半区

                }

                else{

                    low = mid + 1;//插入点在高半区

                }

            }

            int j = i - 1;

            for (j = i - 1; j >= high + 1; --j){

                data[j + 1] = data[j];//记录后移

            }

            data[high + 1] = tem; //插入点

   

        }

    }

}

   

/*

    2-路折半插入排序

*/

void TwoRoadInsertSort(vector<int>& data)

{

    if (data.size() <= 1){

   

    }

    else{

        int midNum = data[0];

        vector<int> highStack, lowStack;

        for (vector<int>::size_type i = 1; i < data.size(); ++i)

        {

            if (data[i] < midNum){

                int low = 0, high = lowStack.size() - 1;

                while (low <= high)

                {

                    int mid = (low + high) / 2;

                    if (lowStack[mid] < data[i]){

                        low = mid + 1; //插入点在高半区

                    }

                    else{

                        high = mid - 1;//插入点在低半区

                    }

                }

                lowStack.push_back(0);

                for (int j = lowStack.size() - 2; j >= high + 1; --j)

                {

                    lowStack[j+1] = lowStack[j];//记录后移

                }

                lowStack[high + 1] = data[i];//准确插入

            }

            else{

                int low = 0, high = highStack.size() - 1;

                while (low <= high)

                {

                    int mid = (high + low) / 2;

                    if (highStack[mid] < data[i]){

                        low = mid + 1;

                    }

                    else{

                        high = mid - 1;

                    }

                }

                highStack.push_back(0);

                for (int j = highStack.size() - 2; j >= high + 1; --j)

                {

                    highStack[j+1] = highStack[j];

                }

                highStack[high + 1] = data[i];

             }

        }

        data.clear();

        for (vector<int>::size_type j = 0; j < lowStack.size(); ++j)

        {

            data.push_back(lowStack[j]);

        }

        data.push_back(midNum);

        for (vector<int>::size_type j = 0; j < highStack.size(); ++j)

        {

            data.push_back(highStack[j]);

        }

    }

}

   

/*

    快速排序

*/

int PartOfQuickSort(vector<int>& data,int low,int high)

{

    

    int key = data[low];

    while (low < high)

    {

        while ((low < high) && (data[high] >= key)){

            --high;

        }

        data[low] = data[high];

        while ((low < high) && (data[low] <= key)){

            ++low;

        }

        data[high] = data[low];

    }

    data[low] = key;

    return low;

}

void QSort(vector<int>& data,int low,int high)

{

    if (low < high)

    {

        int pivotloc = PartOfQuickSort(data, low, high);

        QSort(data, low, pivotloc - 1);

        QSort(data, pivotloc + 1, high);

    }

}

void QuickSort(vector<int>& data)

{

    QSort(data, 0, data.size() - 1);

}

   

/*

    堆排序

*/

inline void Swap(int& a, int& b)

{

    a ^= b;

    b ^= a;

    a ^= b;

}

void HeapAdjust(vector<int>& data, int top, int tail)

{

    int key = data[top];

    for (int i = 2 * top + 1; i <= tail; i = i * 2 + 1)

    {

        i = ((i < tail) && (data[i] < data[i + 1])) ? (i + 1) : i;

        if (key>data[i]){

            break;

        }

        data[top] = data[i];

        top = i;

    }

    data[top] = key;

}

void HeapSort(vector<int>& data)

{

    for (int i = data.size() / 2 - 1; i >= 0; --i)

    {

        HeapAdjust(data, i, data.size()-1);

    }

    for (int i = data.size() - 1; i >= 0; --i)

    {

        Swap(data[0], data[i]);

        HeapAdjust(data, 0, i - 1);

    }

   

}

/*

    归并排序

*/

void Merge(vector<int>& data, int low, int mid, int high)

{

    int s = low, t = mid + 1;

    vector<int> temp;

    while ((s <= mid) && (t <= high))

    {

        if (data[s] < data[t]){

            temp.push_back(data[s]);

            ++s;

        }

        else{

            temp.push_back(data[t]);

            ++t;

        }

    }

    if (s == mid + 1){

        for (int j=t ; j <= high; ++j){

            temp.push_back(data[t++]);

        }

    }

    else{

        for (int j=s ; j <= mid; ++j){

            temp.push_back(data[s++]);

        }

    }

    for (int j=0; j < temp.size(); ++j)

    {

        data[low++] = temp[j];

    }

}

void Merge_S(vector<int>& data, int low, int high)

{

    if (low < high){

        int mid = (low + high) / 2;

        Merge_S(data, low, mid);

        Merge_S(data, mid + 1, high);

        Merge(data, low, mid, high);

    }

}

void MergeSort(vector<int>& data)

{

    Merge_S(data, 0, data.size() - 1);

}

   

void test_StraightInsertSort()

{

    cout << "StraightInsertSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    StraightInsertSort(data);

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

void test_BinaryStraightInsertSort()

{

    cout << "BinaryStraightInsertSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    BinaryStraightInsertSort(data);

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

void test_TwoRoadInsertSort()

{

    cout << "TwoRoadInsertSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    TwoRoadInsertSort(data);

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

void test_QuickSort()

{

    cout << "QuickSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    QuickSort(data);

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

void test_STL_QuickSort()

{

    cout << "STL_QuickSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    sort(data.begin(), data.end());

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

void test_HeapSort()

{

    cout << "HeapSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    HeapSort(data);

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

void test_MergeSort()

{

    cout << "MergeSort " << N << " rand numbers ." << endl;

    SetData(N);

    vector<int> data;

    GetData(data);

   

    DWORD64 start = GetTickCount();

   

    MergeSort(data);

   

    DWORD64 end = GetTickCount();

    cout << "The run time is " << (end - start) << " ms ." << endl;

    SetOrderData(data);

}

int main()

{

    test_StraightInsertSort();

    cout << "------------------------------------" << endl;

    test_BinaryStraightInsertSort();

    cout << "------------------------------------" << endl;

    test_TwoRoadInsertSort();

    cout << "------------------------------------" << endl;

    test_QuickSort();

    cout << "------------------------------------" << endl;

    test_STL_QuickSort();

    cout << "------------------------------------" << endl;

    test_HeapSort();

    cout << "------------------------------------" << endl;

    test_MergeSort();

    cout << "------------------------------------" << endl;

    return 0;

}

 

  • Output
StraightInsertSort 10000 rand numbers .
The run time is 11859 ms .
------------------------------------
BinaryStraightInsertSort 10000 rand numbers .
The run time is 5609 ms .
------------------------------------
TwoRoadInsertSort 10000 rand numbers .
The run time is 4109 ms .
------------------------------------
QuickSort 10000 rand numbers .
The run time is 31 ms .
------------------------------------
STL_QuickSort 10000 rand numbers .
The run time is 141 ms .
------------------------------------
HeapSort 10000 rand numbers .
The run time is 125 ms .
------------------------------------
MergeSort 10000 rand numbers .
The run time is 375 ms .
------------------------------------