常见的排序算法

关于常用的排序算法有：

插入排序：直接插入排序、希尔排序

选择排序：直接选择排序、堆排序

交换排序：冒泡排序、快速排序（4种逐渐优化）

归并排序：归并排序

一下分别给出以上方法具体代码，并且堆快速排序做出几种优化：

（1）子区间优化方法，即可以在最后几层也就是区间不大情况下，直接选择插入排序消耗更少

（2）取key关键字用三数取中的方法，保证它既不是最大也不是最小，提高效率

（3）单趟排序采用挖坑方法

（4）单趟排序采用前后指针的方法

#pragma once  
#include <iostream>  
#include <stack>  
#include <assert.h>  
#include <assert.h>  
using namespace std;  
  
//1.插入排序(直接插入排序)  
void InsertSort(int* a, size_t n)  
{  
    //[0,end] end+1插入到这个有序区间  
    for (size_t i = 0; i < n - 1; i++)//最后一个区间[0,end-2], end-1插入  
    {  
        int end = i;  
        int tmp = a[end + 1];//从第二个数开始插到之前的区间  
  
        //如果要插入的数小于区间末尾那个数，往后挪，依次类推  
        while (end>=0 && tmp < a[end])  
        {  
            a[end + 1] = a[end];//往后挪动  
            --end;//看区间倒数第二个，第三个，等情况，（即找合适位置）  
        }  
        a[end + 1] = tmp;//插入合适位置  
    }  
}  
//时间复杂度：0(N*N)  
  
//2.插入排序(希尔排序)  
void ShellSort(int *a, size_t n)  
{  
    int gap = n;//给区间度量  
  
    while (gap > 1)//区间至少为1进来  
    {  
        //每次以数组长度的1/3作为小区间度量，加1保证最后一定有序  
        gap = gap / 3 + 1;  
        //挨着按照自己的分组进行处理  
        for (size_t i = 0; i < n - gap; i++)  
        {  
            int end = i;  
            int tmp = a[end + gap];  
            while (end >= 0 && a[end] > tmp)//每个分组进行调整  
            {  
                a[end + gap] = a[end];//将一组中大的往后挪动  
                end = end - gap;//一组元素中可能存在多个比要插入的大  
            }  
            a[end + gap] = tmp;  
        }  
    }  
}  
//时间复杂度(O(N^1.3))  
  
  
//3.选择排序，每次选一个最大的最小的放在对应位置，再一次类推  
void SelectSort(int* a, size_t n)  
{  
    assert(a);  
    //定义两个位置，开头和结尾  
    int begin = 0;  
    int end = n - 1;  
    while (begin < end)  
    {  
        //定义最小，最大变量  
        int min = begin;  
        int max = begin;  
        for (size_t i = begin; i <= end; i++)  
        {  
            if (a[i] < a[min])  
            {  
                min = i;//找出最小的  
            }  
            if (a[i] > a[max])  
            {  
                max = i;//找出最大的  
            }  
        }  
        swap(a[max], a[end]);  
        //防止min与end重合了，这是后，end位置元素被max改， 则还原min的位置  
        if (min == end)  
        {  
            min = max;  
        }  
        swap(a[min], a[begin]);  
        //缩小区间以此类推  
        ++begin;  
        --end;  
    }  
}  
  
//4.堆排序  
void AdjustDown(int* a, size_t n, int parent)  
{  
    int child = parent * 2 + 1;  
    while (child < n)  
    {  
        if (child + 1 < n && a[child] < a[child + 1])  
        {  
            ++child;  
        }  
        if (a[child] > a[parent])  
        {  
            swap(a[child], a[parent]);  
            parent = child;  
            child = parent * 2 + 1;  
        }  
        else  
        {  
            break;  
        }  
    }  
}  
void HeapSort(int* a, size_t n)  
{  
    //从最后一个叶子节点的父亲开始调整  
    for (int i = (n - 2) / 2; i >= 0; i--)  
    {  
        AdjustDown(a,n,i);  
    }  
    //排序  
    int end = n - 1;  
    while (end > 0)  
    {  
        swap(a[0],a[end]);  
        AdjustDown(a, end, 0);  
        --end;  
    }  
}  
  
//5.选择排序(冒泡排序)  
void BubbleSort(int* a, size_t n)  
{  
    for (size_t end = n; end > 0; --end)  
    {  
        bool exchange = false;  
        for (size_t i = 1; i < end; i++)  
        {  
            if (a[i - 1] > a[i])  
            {  
                swap(a[i-1],a[i]);  
                //不管哪一趟，只要有交换，就说明不是有序，否则不用调整，直接跳出  
                exchange = true;  
            }  
        }  
        if (exchange == false)  
        {  
            break;  
        }  
    }  
}  
  
//6.快速排序  
//优化方法一：key的选取为三数取中  
int GetMidIndex(int* a, int begin, int end)  
{  
    int mid = begin + (end - begin) << 1;  
    if (a[mid] > a[begin])  
    {  
        if (a[end] > a[mid])  
        {  
            return mid;  
        }  
        else if (a[begin] > a[end])  
        {  
            return begin;  
        }  
        else  
        {  
            return end;  
        }  
    }  
    else//  
    {  
        if (a[mid] > a[end])  
        {  
            return mid;  
        }  
        else if (a[begin] > a[end])  
        {  
            return end;  
        }  
        else  
        {  
            return begin;  
        }  
    }  
  
}  
//优化方法三，单趟排序方法改为挖坑法  
int PartSort1(int* a, size_t begin, size_t end)  
{  
    int key = a[end];  
    while (begin < end)  
    {  
        while (begin < end && a[begin]<=key)  
        {  
            ++begin;  
        }  
        a[end] = a[begin];//填第一个坑，a[begin]为下一个坑  
        while (begin < end && a[end] >= key)  
        {  
            --end;  
        }  
        a[begin] = a[end];  
        //来到这里说明相遇，以及划分好  
    }  
    a[begin] = key;  
    return begin;  
}  
  
//优化方法4，单趟排序为前后指针法  
void PartSort3(int* a, size_t begin, size_t end)  
{  
    int cur = begin;  
    int prev = begin - 1;  
    int key = a[end];  
  
    while (cur < end)  
    {  
        if (a[cur]<key && ++prev!=cur)  
        {  
            swap(a[prev], a[cur]);  
        }  
        ++cur;  
    }  
    //加加prev位置才是大于key的那个  
    swap(a[++prev], a[end]);  
}  
  
  
int PartSort(int* a, size_t begin, size_t end)  
{  
    //选取开头，中间，最后三个位置的中间那个位置下标  
    //int mid = GetMidIndex(a,begin, end);  
    //交换中间那个值与最后一个值  
    //swap(a[mid], a[end]);  
  
    //引用未了最后交换  
    int& key = a[end];  
    //--end;//区间中包括key  
    while (begin < end)  
    {  
        //第一个条件防止begin,end交错了  
        while (begin < end && key >= a[begin])  
        {  
            ++begin;  
        }  
        while (begin < end && key <= a[end])  
        {  
            --end;  
        }  
        //找到大的，小的  
        swap(a[begin], a[end]);  
    }  
    //begin地方比key大，因为它先停下来  
      
    //单一解决有序的问题，还有待考虑。  
    //if(key<a[begin])  
        swap(a[begin],key);  
    return begin;  
  
}  
  
  
  
void QuikSort(int* a, int left, int right)  
{  
    if (left >= right)//区间为1，已经有序，停止  
    {  
        return;  
    }  
  
    //优化方法2，子区间优化，最后基层不用快速排序，二用插入排序  
    //if (right - left < 16)  
    //{  
    //  //注意是a+left,不是a,是单独一块空间  
    //  InsertSort(a+left, right-left+1);  
    //}  
    int mid = PartSort1(a, left, right);  
    QuikSort(a, left, mid - 1);  
    QuikSort(a, mid+1, right);  
}  
  
  
//非递归实现快速排序  
void QuikSortNonR(int* a, int left, int right)  
{  
    stack<int> s;  
    //先压右区间进去，再压左区间，出来的时候，先出左，再出右  
    s.push(right);  
    s.push(left);  
  
    while (!s.empty())//只要栈不空，说明有里面还有区间  
    {  
        int begin = s.top();  
        s.pop();  
        int end = s.top();  
        s.pop();  
  
        //去区间出来你，按照快速排序走一趟  
        int mid = PartSort1(a,begin, end);  
        //根据需要，再将分开的2遍再次入栈，进行下一轮快拍  
        if (begin < mid - 1)  
        {  
            s.push(mid-1);  
            s.push(begin);  
        }  
        if (mid + 1 < end)  
        {  
            s.push(end);  
            s.push(mid+1);  
        }  
    }  
}  
  
//归并排序  
void MergeSort(int* a, size_t n)  
{  
    assert(a);  
    int* tmp = new int[n];  
    _MergeSort(a,0,n-1,tmp);  
    delete[] tmp;  
}  
//使得左右2边有序，并且归并  
void _MergeSort(int* a, int left, int right, int* tmp)  
{  
    if (left >= right)//当区间缩到1时，停止递归  
    {  
        return;  
    }  
    int mid = left + ((right - left) >> 1);  
  
    _MergeSort(a, left, mid, tmp);  
    _MergeSort(a, mid+1, right, tmp);  
  
    int begin1 = left;  
    int end1 = mid;  
    int begin2 = mid+1;  
    int end2 = right;  
  
    size_t index = left;  
  
    //归并  
    while (begin1 <= end1 && begin2 <= end2)  
    {  
        if (a[begin1] >= a[begin2])  
        {  
            tmp[index++] = a[begin2++];  
        }  
        else  
        {  
            tmp[index++] = a[begin1++];  
        }  
    }  
    //出来之后，对剩下的归并  
    while (begin1 <= end1)  
    {  
        tmp[index++] = a[begin1++];  
    }  
    while (begin2 <= end2)  
    {  
        tmp[index++] = a[begin2++];  
    }  
    //拷贝  
    memcpy(a+left, tmp+left, (right-left+1)*sizeof(int));  
}  
  
  
  
  
  
  
void test()  
{  
    int a[] = {1,3,6,9,5,7,1,9,6};  
  
    int a[] = { 1,3,9,6,8,2,4,7,0,5 };  
    size_t n = sizeof(a)/sizeof(a[0]);  
    InsertSort(a, n);  
    ShellSort(a, n);  
    SelectSort(a, n);  
    HeapSort(a,n);  
    BubbleSort(a, n);  
    QuikSort(a, 0, n-1);  
    QuikSortNonR(a, 0, n - 1);  
    for (size_t i = 0; i < n; i++)  
    {  
        cout << a[i] << " ";  
    }  
    cout << endl;  
}