数据结构之排序总结

Posted by jjx on July 11, 2016

冒泡排序

冒泡排序(Bubble Sort),又被称为气泡排序或泡沫排序。

它是一种较简单的排序算法。它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小;如果前者比后者大,则交换它们的位置。这样,一次遍历之后,最大的元素就在数列的末尾! 采用相同的方法再次遍历时,第二大的元素就被排列在最大元素之前。重复此操作,直到整个数列都有序为止!

冒泡排序时间复杂度

冒泡排序的时间复杂度是O(N^2)。 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢?N-1次!因此,冒泡排序的时间复杂度是O(N2)。

冒泡排序稳定性

冒泡排序是稳定的算法,它满足稳定算法的定义。
算法稳定性 – 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

实现

/**
 * 冒泡排序:C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 * 冒泡排序
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
void bubbleSort1(int* a, int n)
{
    int i,j,tmp;

    for (i=n-1; i>0; i--)
    {
        // 将a[0...i]中最大的数据放在末尾
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
            {    
                // 交换a[j]和a[j+1]
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

/*
 * 冒泡排序(改进版)
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
void bubbleSort2(int* a, int n)
{
    int i,j,tmp;
    int flag;                 // 标记

    for (i=n-1; i>0; i--)
    {
        flag = 0;            // 初始化标记为0

        // 将a[0...i]中最大的数据放在末尾
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
            {
                // 交换a[j]和a[j+1]
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;

                flag = 1;    // 若发生交换,则设标记为1
            }
        }

        if (flag==0)
            break;            // 若没发生交换,则说明数列已有序。
    }
}

int main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    bubbleSort1(a, ilen);
    //bubbleSort2(a, ilen);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

快速排序

快速排序(Quick Sort)使用分治法策略。
它的基本思想是:选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序流程:
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边) ;在这个分区退出之后,该基准就处于数列的中间位置。
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。

快速排序的时间复杂度和稳定性

快速排序稳定性
快速排序是不稳定的算法,它不满足稳定算法的定义。
算法稳定性 – 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

快速排序时间复杂度
快速排序的时间复杂度在最坏情况下是O(N2),平均的时间复杂度是O(N*lgN)。
这句话很好理解:假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢?至少lg(N+1)次,最多N次。 (01) 为什么最少是lg(N+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。因此,快速排序的遍历次数最少是lg(N+1)次。
(02) 为什么最多是N次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。

/**
 * 快速排序:C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 * 快速排序
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     l -- 数组的左边界(例如,从起始位置开始排序,则l=0)
 *     r -- 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)
 */
void quickSort(int* a, int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; // 从右向左找第一个小于x的数
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; // 从左向右找第一个大于x的数
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quickSort(a, l, i-1); /* 递归调用 */
        quickSort(a, i+1, r); /* 递归调用 */
    }
}

int main()
{
    int i;
    int a[] = {30,40,60,10,20,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    quickSort(a, 0, ilen-1);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

直接插入排序

直接插入排序(Straight Insertion Sort) 的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

直接插入排序时间复杂度
直接插入排序的时间复杂度是O(N2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢?N-1!因此,直接插入排序的时间复杂度是O(N2)。

直接插入排序稳定性
直接插入排序是稳定的算法,它满足稳定算法的定义。
算法稳定性 – 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

/**
 * 直接插入排序:C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 * 直接插入排序
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
void insertSort(int* a, int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        //如找到了一个合适的位置
        if (j != i - 1)
        {
            //将比a[i]大的数据向后移
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            //将a[i]放到正确位置上
            a[k + 1] = temp;
        }
    }
}

int main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    insertSort(a, ilen);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

希尔排序

希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

希尔排序实质上是一种分组插入方法。它的基本思想是:对于n个待排序的数列,取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列,所有距离为gap的倍数的记录放在同一个组中;然后,对各组内的元素进行直接插入排序。 这一趟排序完成之后,每一个组的元素都是有序的。然后减小gap的值,并重复执行上述的分组和排序。重复这样的操作,当gap=1时,整个数列就是有序的

希尔排序时间复杂度
希尔排序的时间复杂度与增量(即,步长gap)的选取有关。例如,当增量为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为O(N²),而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。

希尔排序稳定性
希尔排序是不稳定的算法,它满足稳定算法的定义。对于相同的两个数,可能由于分在不同的组中而导致它们的顺序发生变化。

/**
 * 希尔排序:C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 * 希尔排序
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
void shellSort1(int* a, int n)
{
    int i,j,gap;

    // gap为步长,每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组,对每一组都执行直接插入排序
        for (i = 0 ;i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap) 
            {
                // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }

    }
}

/*
 * 对希尔排序中的单个组进行排序
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组总的长度
 *     i -- 组的起始位置
 *     gap -- 组的步长
 *
 *  组是"从i开始,将相隔gap长度的数都取出"所组成的!
 */
void groupSort(int* a, int n, int i,int gap)
{
    int j;

    for (j = i + gap; j < n; j += gap) 
    {
        // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
        if (a[j] < a[j - gap])
        {
            int tmp = a[j];
            int k = j - gap;
            while (k >= 0 && a[k] > tmp)
            {
                a[k + gap] = a[k];
                k -= gap;
            }
            a[k + gap] = tmp;
        }
    }
}

/*
 * 希尔排序
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
void shellSort2(int* a, int n)
{
    int i,gap;

    // gap为步长,每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组,对每一组都执行直接插入排序
        for (i = 0 ;i < gap; i++)
            groupSort(a, n, i, gap);
    }
}

int main()
{
    int i;
    int a[] = {80,30,60,40,20,10,50,70};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    shellSort1(a, ilen);
    //shellSort2(a, ilen);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}