c++实现常用排序算法(全)

冒泡、插入、希尔、归并、快速、堆

#include<iostream>
#include<vector>

using namespace std;

class ALLSORT
{
public:
    ALLSORT() {};

    //冒泡
    void bubble(vector<int>& numList)
    {
        int n = numList.size();
        for (int i = 0; i < n; i++)
        {
            bool isSwap = false;
            for (int j = i + 1; j < n; j++)
            {
                if (numList[i] > numList[j])
                {
                    swap(numList[i], numList[j]);
                    isSwap = true;
                }
            }
            if (!isSwap) return;
        }
    }

    //插入排序(对已经比较有序的数组比较高效)
    void insertSort(vector<int>& numList)
    {
        int n = numList.size();
        for (int i = 1; i < n; i++) //当前处理的值
        {
            int dataTemp = numList[i];
            int j=i;
            for (j ; j > 0; j--) //注意判断条件j-1
            {
                if( dataTemp <= numList[j-1] ) numList[j] = numList[j - 1]; //右移
            }
            //cout << j << dataTemp << endl;
            numList[j] = dataTemp; //最后一个合适位置放处理的值
        }
    }

    //希尔排序(改进的插入排序)
    void shellSort(vector<int>& numList)
    {
        int n = numList.size();
        for (int gap=n/2;gap > 0;gap/=2)
        {
            for (int i = gap; i < n; i++)
            {
                int dataTemp = numList[i];
                int j=i;
                for (j ; j - gap >= 0 && dataTemp <= numList[j - gap]; j -= gap)
                {
                    numList[j] = numList[j - gap];
                }
                numList[j] = dataTemp;
            }
        }
    }

    //选择排序
    void selectionSort(vector<int>& numList)
    {
        int n = numList.size();
        for (int i = 0; i < n-1; i++) //只需要遍历n-1次
        {
            int index = i;
            int j = i+1;
            for (j; j < n; j++) //找到最小元素所在下标
            {
                if (numList[j] < numList[index]) index = j;
            }
            if (index != i)
            {
                swap(numList[i], numList[index]); //交换当前处理值和当前批次最小的下标值
            }
        }
    }

    //快速排序
    void quickSort(vector<int>& numList, int start, int end)
    {
        if (start > end) return;
        int l = start, r = end;
        int dataTemp = numList[start];

        while (l != r)
        {

            while (l < r && numList[r] > dataTemp) //找第一个比基数小的
            {
                r--;
            }

            while (l < r && numList[l] <= dataTemp) //找第一个比基数大的,因为选取的基数是最左边，必须要小于等于，注意
            {
                l++;
            }
            if (l < r) swap(numList[l], numList[r]); //交换第一个比基数小和第一个比基数大的两个值
        }

        numList[start] = numList[l]; //交换基数和最后位置的值
        numList[l] = dataTemp;

        quickSort(numList, start, l - 1); //处理基数左边的
        quickSort(numList, l+1, end); //处理基数右边的

    }

    //归并排序
    void mergeSort(vector<int>& numList, int start, int end)
    {
        if (start >= end) return;
        int n = end - start + 1;
        int middle = start + (end - start) /2;

        mergeSort(numList, start, middle); //递归
        mergeSort(numList, middle + 1, end);

        vector<int> newList(n); //开辟新空间
        int pivot =0, l=start, r=middle+1;
        while (l <= middle && r <= end)
        {
            newList[pivot++] = numList[l] < numList[r] ? numList[l++] : numList[r++];
        }
        while (l <= middle) //加上剩余的值
        {
            newList[pivot++] = numList[l++];
        }
        while (r <= end)
        {
            newList[pivot++] = numList[r++];
        }
        for (int i = 0; i < n; i++)
        {
            numList[start++] = newList[i];
        }

    }

    //堆排序
    void heapSort(vector<int>& numList)
    {
        int n = numList.size();

        //初始化构建堆（从最后一个非叶子结点开始，向后调整）
        for (int i = n/2-1; i >=0 ; --i)
        {
            heapify(numList, i, n);
        }

        //调整堆（向前调整）
        for (int i = n - 1; i > 0; --i) //注意是大于0
        {
            swap(numList[0], numList[i]);  //交换第一和最后一个位置
            heapify(numList, 0, i);
        }
    }

    void heapify(vector<int>& numList, int start, int end)
    {
        int father = start;
        int son = father * 2 + 1;
        while (son < end)
        {
            //找到子树中最大的
            if (son + 1 < end && numList[son] < numList[son + 1]) ++son;

            //比较父节点和最大子节点
            if (numList[son] < numList[father]) break;
            else
            {
                swap(numList[son], numList[father]);//交换父子
                father = son;
                son = 2 * father + 1;

            }
        }
    }

};


//void main()
//{
//    vector<int> numList = { 8,9,5,1,33,4,16,55,2,0,4,7,3,2,14,5,17,6,3 };
//    ALLSORT sortHelper;
//    //sortHelper.heapSort(numList);
//    sortHelper.quickSort(numList, 0, numList.size()-1);
//    for (auto i : numList)
//    {
//        cout << i << endl;
//    }
//
//}