数据结构之排序算法

1. 冒泡排序

基本思想：每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。

时间复杂度：

• 最好的情况下，待排序记录已经有序，只需要一趟排序就可以完成，所以冒泡排序的最好时间复杂度为 O(n)。
• 最坏的情况下，待排序记录反序，这时需要 n - 1 趟排序，每趟排序需要比较 n - i 次比较操作，这时比较和移动的次数达到最大值，所以冒泡排序的最坏时间复杂度为 O(n ^ 2)。
• 平均时间复杂度为 O(n ^ 2)。因为它移动的次数较多，其平均时间性能还不如直接插入排序。

void bubble_sort(int s[],int n)
{
    for (int i=0;i<n;i++)
    {
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
            }
        }
    }
}

冒泡排序的优化：在算法中增加一个标志exchange，用以标识本趟冒泡结果是否发生了交换；如果没有发生交换则exchange=false，表示全部元素已经排好，因而可以结束算法；如果exchange=true，表示本趟有元素发生交换，还需执行下一趟排序。

void new_bubble_sort(int s[],int n)
{
    bool exchange;
    for (int i=0;i<n;i++)
    {
        exchange = false;
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
                exchange =true;
            }
        }
        if(exchange == false)   return;
    }
}

2. 插入排序

基本思想：每次将一个待排序元素按其大小插入到前面已经排好的序列中的适当位置，直至元素全部插入为止

时间复杂度分析： 直接插入排序算法主要进行有两个操作，查找比较，移动记录。这两个操作均和记录长度n相关。其平均时间复杂度为O(n^2)。这在排序算法里面算慢的，但是当记录较少时，它的效率还是可以不错的。

空间复杂度分析：直接插入排序只需要一个元素的辅助空间，用于元素的位置交换O(1)。

直接插入排序是稳定排序。它在元素基本有序的情况下（接近最好情况），比较和移动的次数都较少，效率是很高的。

2.1 直接插入排序

void insert_sort(int s[],int n)
{
    for (int i=1;i<n;i++)
    {
        if (s[i]<s[i-1])
        {
            int temp = s[i], j=i-1;
            do 
            {
                s[j+1] = s[j];
                j--;
            } 
            while (j>=0 && temp<s[j]);
            s[j+1] = temp;
        }
    }
}

2.2 二分插入排序

利用二分查找，查找待插入元素应插入前面有序序列的位置。

3. 选择排序

基本思想：每次（第i次）在后面待排序元素中选出排序码最小的元素，作为有序元素序列的第i个元素。待n-2趟作完，待排序元素只剩下1个，就不用排序了。

时间复杂度分析：无论待排序记录的初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：n*(n-1) /2=O(n^2)，当待排序记录的初始状态为正序时，移动次数为 0；当初始状态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3 *(n-1)。所以，直接选择排序的平均时间复杂度为O(n^2)。

非稳定排序。

void select_sort(int s[],int left,int right)
{
    for (int i=left;i<right;i++)
    {
        int min = i;
        for (int j=i+1;j<=right;j++)
        {
            if(s[j]<s[min]) min = j;
        }
        if(min != i)    swap(s[i],s[min]);
    }
}

4. 快速排序

时间复杂度分析：

• 最坏情况：每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。此时，时间复杂度为 O(n ^ 2)。
• 最好情况：每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：0(nlgn)。
• 尽管快速排序的最坏时间为 O(n ^ 2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为 O(nlgn)。

空间复杂度分析：快速排序需要一个栈来实现递归。若每次划分较为均匀（也就是对半分，基准值总是中值），则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

int partition(int s[],int low,int high)
{
    int key = s[high];
    int piv = low;
    for (int i=low;i<high;i++)
    {
        if (s[i]<=key)
        {
            swap(s[piv],s[i]);
            piv++;
        }
    }
    swap(s[piv],s[high]);
    return piv;
}

void quick_sort(int s[],int left,int right)
{
    if (left<right)
    {
        int piv = partition(s,left,right);
        quick_sort(s,left,piv-1);
        quick_sort(s,piv+1,right);
    }
}

5. 归并排序

归并排序是采用分治法的一个非常典型的应用，它要做两件事情：

• “分”, 就是将数组尽可能的分，一直分到原子级别；
• “并”，将原子级别的数两两合并排序，最后产生结果。

至于二个有序数列合并，只要比较二个数列的第一个数，谁小就先取谁安放到临时队列中，取了后将对应数列中这个数删除，直到一个数列为空，再将另一个数列的数据依次取出即可。

void merge(int* array, int tempArray, int left, int middle, int right)
{
    for(int i=left;i<=right;i++)    tempArray[i] = array[i];
    int s1 = left, s2 = mid +1, temp = left;
    while(s1 <=mid && s2 <= right)
    {
        if(tempArray[s1] <= tempArray[s2])
            array[temp++] = tempArray[s1++];
        else    array[temp++] = tempArray[s2++];
    }
    while(s1 <= mid) array[temp++] = tempArray[s1++];
    while(s2 <= right) array[temp] = tempArray[s2++];
}

void merge_sort(int* array, int* tempArray, int left, int right)
{
    if(left >= right)   return ;
    int mid = left + (right - left)/2;
    int tempArray = new int[right-left+1];
    merge_sort(array,tempArray,left,mid);
    merge_sort(array,tempArray,mid+1,right);
    merge(array,tempArray,left,mid,right);
}