排序算法总结

注意： 快速排序是排序大数组的最常用算法
 

排序算法	平均时间	最差时间	稳定度	额外空间	备注说明
冒泡排序	O(n2)	O(n2)	稳定	O(1)	n小时较好
选择排序	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入排序	O(n2)	O(n2)	稳定	O(1)	n小时较好
归并排序	O(nlogn)	O(nlogn)	稳定	O(n)	n大时较好
快速排序	O(nlogn)	O(n2)	不稳定	O(logn)	n大时较好
堆排序	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好
计数排序	O(n)	O(n)	稳定	O(n+k)	输入序列限制
基数排序	O(n)	O(n)	稳定	O(n+k)	输入序列限制
桶排序	O(n)	O(n)	稳定	O(n)	输入序列限制

下表是各个排序算法的比较说明

 

插入排序：

是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度：O(n^2)，空间复杂度：O(1)。是稳定的排序方法。

void InsertionSort(int *a,int n)
{
    int temp;
    for(int i = 1;i < n;++i)
    {
        temp = *(a + i);
        int j = i - 1;
        while(j >= 0 && *(a + j) > temp)
        {
            *(a + j + 1) = *(a + j);
            --j;
        }
        *(a + j + 1) = temp;
    }
}

合并排序
采用分治法。将n个元素分成各含n/2个元素的子序列，用合并排序法对两个子序列递归的排序(子序列长度为1时递归结束)，最后合并两个已排序的子序列得到结果。时间复杂度：O(nlogn)，空间复杂度：O(n)。是稳定的排序方法。

//合并排序

#include <iostream>
using namespace std;

#define MAX_VALUE 100000//用于设置哨兵，避免检查是否每一个堆都是空的

//合并两个子数组的函数
void Merge(int *a,int p,int q,int r)
{
    int num1,num2;
    num1 = q - p + 1;
    num2 = r - q;
    int *a1 = (int*)malloc((num1 + 1) * sizeof(int));
    int *a2 = (int*)malloc((num2 + 1) * sizeof(int));
    for(int i = 0;i < num1;++i)
        *(a1 + i) = *(a + p + i);
    *(a1 + num1) = MAX_VALUE;//设置哨兵元素
    for(int i = 0;i < num2;++i)
        *(a2 + i) = *(a + q + 1 + i);
    *(a2 + num2) = MAX_VALUE;//设置哨兵元素

    //进行排序
    int index1 = 0;
    int index2 = 0;
    for(int i = p;i <= r;++i)
    {
        if(*(a1 + index1) < *(a2 + index2))
        {
            *(a + i) = *(a1 + index1);
            ++index1;
        }
        else
        {
            *(a + i) = *(a2 + index2);
            ++index2;
        }
    }
    free(a1);
free(a2);
}

冒泡排序

每一趟都比较相邻两个元素，若是逆序的，则交换。结束的条件应该是“在一趟排序过程中没有进行过交换元素的操作”。时间复杂度：O(n^2)，空间复杂度O(1)。是稳定的排序。

void BubbleSort(int *a,int n)
{
    int flag,temp;//标记是否进行过交换操作
    for(int i = 0;i < n - 1;++i)
    {
        flag = 0;
        for(int j = 0;j < n - 1 - i;++j)
        {
            if(*(a + j) > *(a + j + 1))
            {
                temp = *(a + j);
                 *(a + j) = *(a + j + 1);
                 *(a + j + 1) = temp;
                 flag = 1;
            }
        }
        if(flag == 0)break;
    }
}

快速排序

它是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序元素分成两个部分，其中一部分元素比另一部分元素小。再分别对这两部分元素进行排序。以达到整个元素序列有序。时间复杂度：O(nlogn)，空间复杂度O(logn)，是不稳定的算法。

int Partition(int *a,int low,int high)
{
    int pivotKey = *(a + high);
    int i = low - 1;
    for(int j = low;j <= high - 1;++j)
    {
        if (*(a + j) < pivotKey)
        {
            ++i;
            int tmp = *(a + i);
            *(a + i) = *(a + j);
            *(a + j) = tmp;
        }
    }

    int tmp = *(a + i + 1);
    *(a + i + 1) = *(a + high);
    *(a + high) = tmp;

    return (i + 1);
}

void QuickSort(int *a,int low,int high)
{
    if(low < high)
    {
        int PivotLoc = Partition(a,low,high);
        QuickSort(a,low,PivotLoc - 1);
        QuickSort(a,PivotLoc + 1,high);
    }
}

堆排序：
一种原地排序算法，即在任何时刻数组中只有常数个元素存储在输入数组以外

//注意：下表都以1开始，而不是0
//得到父节点索引
int getParent(int i)
{
    return i>>1;
}

//得到左子树索引
int getLeftSon(int i)
{
    return i<<1;
}

//得到右子树索引
int getRightSon(int i)
{
    return ((i<<1) + 1);
}

//调整以某个节点i为根节点的子树为大根堆
void MaxHeapify(int A[],int i,int HeapSize)
{
    int left = getLeftSon(i);
    int right = getRightSon(i);
    int largest = i;//记录值最大的元素的索引

    if (left <= HeapSize && A[left] > A[i])
    {
        largest = left;
    }

    if (right <= HeapSize && A[right] > A[largest])
    {
        largest = right;
    }

    if (largest != i)//此子树不满足大根堆的性质，需要进行调整
    {
        //进行交换
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;

        MaxHeapify(A,largest,HeapSize);//递归调用，继续调整子树
    }
}

//输出数组元素
void printHeap(int A[],int HeapSize)
{
    for(int i = 1;i <= HeapSize;++i)
    {
        cout << A[i] << " ";
    }
    cout << endl;
}

//建堆
void buildMaxHeap(int A[],int HeapSize)
{
    for (int i = (int)floor((float)HeapSize / 2);i > 0;--i)
    {
        MaxHeapify(A,i,HeapSize);
    }

    cout << "建成的大根堆：" << endl;
    printHeap(A,HeapSize);
}

//堆排序
void heapSort(int A[],int HeapSize)
{
    buildMaxHeap(A,HeapSize);
    for (int i = HeapSize;i > 0;--i)
    {
        int temp = A[1];
        A[1] = A[i];
        A[i] = temp;
        MaxHeapify(A,1,i - 1);
    }
}

计数排序

思想是对每一个输入元素x，确定出小于x的元素的个数。然后我们就可以直接把它放在嘴中输出数组中相应的位置上。 但是计数排序基于这样一个假设：n个输入元素的每一个大小范围都是[0,k]。

void CountintSort(int A[],int *B,int n,int k,int *C)
{
    //初始化C数组
    for (int i = 0;i <= k;++i)
    {
        C[i] = 0;
    }

    for (int i = 0;i < n;++i)
    {
        ++C[A[i]];//C[i]：值等于i的元素的个数
    }

    for (int i = 1;i <= k;++i)
    {
        C[i] += C[i - 1];//C[i]：值小于等于i的元素的个数
    }

    for (int i = n - 1;i >= 0;--i)
    {
        B[C[A[i]] - 1] = A[i];//注意：下标索引从0开始！
        --C[A[i]];
    }
}

时间复杂度是O(k + n)。一般，当k = O(n)时，常常采用计数排序。这时候的运行时间为O(n)。计数排序是稳定的排序。

基数排序

算法思想

基数排序是从低位到高位依次对所有的数进行排序。如果所有的数最高位数是d，那么先按最低有效位数字进行排序，得到一个结果。然后往高位重复这个过程。需要注意的是，按位排序必须是稳定的排序算法。经常采用的是计数排序。

/********************************************************
*函数名称：GetNumInPos
*参数说明：num 一个整形数据
*         pos 表示要获得的整形的第pos位数据
*说明： 找到num的从低到高的第pos位的数据
*********************************************************/
int GetNumInPos(int num,int pos)
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}

/********************************************************
*函数名称：RadixSort
*参数说明：pDataArray 无序数组；
*         iDataNum为无序数据个数
*说明： 基数排序
*********************************************************/
#define RADIX_10 10 //整形排序
#define KEYNUM_31 10 //关键字个数，这里为整形位数
void RadixSort(int* pDataArray, int iDataNum)
{
    int *radixArrays[RADIX_10]; //分别为0~9的序列空间
    for (int i = 0; i < 10; i++)
    {
        radixArrays[i] = (int*)malloc((iDataNum + 1)*sizeof(int));
        radixArrays[i][0] = 0; //index为0处记录这组数据的个数
    }

    for (int pos = 1; pos <=KEYNUM_31; pos++) //从个位开始到KEYNUM_31位
    {
        for (int i = 0; i < iDataNum; i++) //分配过程
        {
            int num = GetNumInPos(pDataArray[i], pos);
            int index = ++radixArrays[num][0];
            radixArrays[num][index] = pDataArray[i];
        }

        int j;
        for (i = 0, j =0; i < RADIX_10; i++) //收集
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                pDataArray[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0; //复位
        }
    }
}

桶排序

当输入数据符合均匀分布时，即可以以线性期望时间运行。即使输入不满足线性关系，桶排序也仍然可以以线性时间运行。只要输入满足这样一个性质，即各个桶尺寸的平方和与总的元素数呈线性关系。

桶排序的思想：
将区间[0,1)分成n个相同大小的子区间，或称为桶。然后将n个输入元素分布到各个桶中去。每个桶中的元素用一个链表来存储

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

//桶中链表节点数据结构
typedef struct StructLinkNode{
    double elem;
    struct StructLinkNode *next;
}LinkNode,*LinkNodePtr;

//桶排序
void BucketSort(double *a,int n);
//删除一条链表
void deleteLinkList(LinkNodePtr head);

int main()
{
    srand(time(NULL));
    int n = 8;
    double *a = new double[n];
    for(int i = 0;i < n;++i)
        *(a + i) = rand() * 1.0 / RAND_MAX;

    cout << "Before sort : " << endl;
    for(int i = 0;i < n;++i)
        cout << *(a + i) << " ";
    cout << endl;

    BucketSort(a,n);

    cout << "After sort : " << endl;
    for(int i = 0;i < n;++i)
        cout << *(a + i) << " ";
    cout << endl;
}

//桶排序
void BucketSort(double *a,int n)
{
    //存放链表的数组
    LinkNodePtr *linkListArr = new LinkNodePtr[n];
    //初始化
    for (int i = 0;i < n;++i)
    {
        linkListArr[i] = new LinkNode;
        linkListArr[i]->elem = -1;
        linkListArr[i]->next = NULL;
    }

    //将n个输入元素依次放入n个桶中
    for (int i = 0;i < n;++i)
    {
        LinkNodePtr newNode = new LinkNode;
        newNode->elem = *(a + i);
        newNode->next = NULL;

        //将新元素插入对应桶的链表的正确位置
        int index = floor(n * *(a + i));
        LinkNodePtr loopPtr = linkListArr[index]->next;
        LinkNodePtr prevPtr = linkListArr[index];
        while(loopPtr != NULL && *(a + i) > loopPtr->elem)
        {
            prevPtr = loopPtr;
            loopPtr = loopPtr->next;
        }
        newNode->next = loopPtr;
        prevPtr->next = newNode;
    }

    int count = 0;
    for (int i = 0;i < n;++i)
    {
        LinkNodePtr loopPtr = linkListArr[i]->next;
        while(loopPtr != NULL)
        {
            *(a + count) = loopPtr->elem;
            ++count;
            loopPtr = loopPtr->next;
        }
    }

    for (int i = 0;i < n;++i)
        deleteLinkList(linkListArr[i]);
}

//删除一条链表
void deleteLinkList(LinkNodePtr head)
{
    if (NULL == head)
    {
        return;
    }
    deleteLinkList(head->next);
    delete head;
}