常见的排序算法（国嵌学习笔记）

一、排序的概念及分类

1>排序的一般定义

    排序是计算机内京城进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。

2>排序的数学定义

    假设含n个数据元素的序列为{R1，R2，R3，...,Rn},其相应的关键字序列为{K1，K2，...,Kn}这

些关键字相互之间可以进行比较，即在他们之间存在着这样一个关系：

        Kp1<=Kp2<=...<=Kpn

按此固有关系将上式记录序列重新排列为{Rp1，Rp2，...,Rpn}的操作称作排序。

3>排序的稳定性

    如果在序列中有两个数据元素r[i]和r[j],它们的关键字k[i]==k[j],且在排序之前，对象r[i]排

在r[j]前面。如果排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这

个排序方法是不稳定的。

4>多关键字排序

    排序时需要比较的关键字多余一个，排序结果首先按关键字1进行排序，当关键字1相同时按关键

字2进行排序，......当关键字n-1相同时则按关键字n进行排序，以此类推。

5>排序中的关键操作

    比较：任意两个数据元素通过比较操作确定先后次序。

    

    交换：数据元素之间需要交换才能得到预期结果。

6>内排序和外排序

    内排序：整个排序过程中不需要访问外存便能完成

    外排序：待排序的数据元素数量很大，整个序列的排序过程不可能在内存中完成。

7>排序的审判

时间性能

    关键性能差异体现在比较和交换的数量

辅助存储空间

    为完成排序操作需要的额外的存储空间，必要时可以“空间换时间”。

算法的实现复杂性

    过于发杂的排序会影响代码的可读性和可维护性，也可能影响排序的性能。

二、选择排序：

1>基本思想：

    每一趟（例如第i趟，i = 0,1,...,n - 2）在后面n - i个待排的数据元素中选出关键字最小的

元素，作为有序元素序列的第 i 个元素。

2>代码实现：

/**********************SelectionSort.c*********************************/
#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void println(int array[], int len)
{
    int i = 0;
    for(i=0; i<len;i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void SelectionSort(int array[], int len) //O(n*n)
{
    int i = 0;
    int j = 0;
    int k = -1;
    for(i=0;i<len;i++)
    {
        k = i;
        for(j=i;j<len;j++)
        {
            if( array[j] < array[k] )
            {
                k = j;
            }
        }
        swap(array, i ,k);
    }
}

int main(int argc, char *argv[])
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    println(array,len);
    SelectionSort(array,len);
    println(array,len);
    return 0;
}

三、插入排序

1>基本思想：

    当插入第i（i >= 1）个数据元素时，前面的v[0],v[1],...,v[i-1]已经排好序。这时，用v[i]

的关键字与v[i-1],v[i-2],...的关键字进行比较，找到插入位置即将v[i]插入，原来位置上的对象

向后顺移。

2>代码实现：

/**********************InsertionSort.c*********************************/
#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void println(int array[], int len)
{
    int i = 0;
    for(i=0; i<len;i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void InsertionSort(int array[], int len) //O(n*n)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;
    for(i=0;i<len;i++)
    {
        k = i;
        temp = array[k];
        for(j=i-1; (j>=0) && (array[j]>temp); j--)
        {
            array[j+1] = array[j];
            k = j;
        }
        array[k] = temp;
    }
}

int main(int argc, char *argv[])
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    println(array,len);
    InsertionSort(array,len);
    println(array,len);
    return 0;
}

四、冒泡排序：

    

1>基本思想：

    设待排数据元素序列中的元素个数为n。最多作n-1趟，i=1,2,...，n-1在第i趟中从后向前，

j=n-1,n-2,...,i,两两比较v[j-1]和v[j]的关键字。如果发生逆序，则交换v[j-1]和v[j].

2>代码实现：

/*********************BuubleSort.c****************************************/
#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void println(int array[], int len)
{
    int i = 0;
    for(i=0; i<len;i++)
    {
    printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void BubbleSort(int array[], int len) //O(n*n)
{
    int i = 0;
    int j = 0;
    int exchange = 1;
    for(i=0; (i<len) && exchange; i++)
    {
        exchange = 0;
        for(j=len-1; j>i; j--)
        {
            if( array[j] < array[j-1] )
            {
                swap(array,j, j-1);
                exchange = 1;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    println(array,len);
    BubbleSort(array,len);
    println(array,len);
    return 0;
}

五、希尔排序（不稳定）

1>基本思想：

    将排序序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序

列进行插入排序。

2>代码实现：

/********************ShellSort.c*****************************/

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void println(int array[], int len)
{
    int i = 0;
    for(i=0; i<len;i++)
    {
    printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void ShellSort(int array[], int len) //O(n*n)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;
    int gap = len;
    do
    {
        gap = gap / 3 + 1; /*gap的值必须最后收敛于1*/
        for(i= gap; i<len; i+=gap)
        {
            k = i;
            temp = array[k];
            for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
            {
                array[j+gap] = array[j]    ;
                k = j;
            }
            array[k] = temp;
        }
    }while(gap > 1);
}

int main(int argc, char *argv[])
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    println(array,len);
    ShellSort(array,len);
    println(array,len);
    return 0;
}

六、快速排序(不稳定)

1>基本思想：

    1）任取待排序序列中的某个数据元素（例如：第一个元素）作为基准，按照该元素的关键字大

小将整个序列划分为左右两个序列：

    *左侧子序列中所有的元素都小于或等于基准元素

    *右侧子序列元素中所有元素都大于基准元素

    *基准元素排在这两个子序列中间

    2）分别对这两个自序列重复施行上述方法，知道所有的对象都排在相应位置上为止。

    3）首先对无序的记录序列进行一次划分，之后分别对分割所得两个子序列递归进行快速排序。

2>实现代码：

/*********************QuickSort.c*******************************/

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void println(int array[], int len)
{
    int i = 0;
    for(i=0; i<len;i++)
    {
    printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

int partition(int array[], int low, int high)//
{
    int pv = array[low];
    while( low < high )
    {
        while( (low < high ) && (array[high] >= pv))
        {
            high--;
        }
        swap(array,low,high);
        while( (low < high) && (array[low] <= pv) )
        {
            low++;
        }
        swap(array,low,high);
    }
    return low;
}

void QSort(int array[], int low, int high)
{
    if(low < high)
    {
        int pivot = partition(array,low,high);
        QSort(array,low,pivot-1);
        QSort(array,pivot+1,high);
    }
}

void QuickSort(int array[], int len) //O(n*logn)
{
    QSort(array,0,len-1);
}

int main(int argc, char *argv[])
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    println(array,len);
    QuickSort(array,len);
    println(array,len);
    return 0;
}

七、归并排序(稳定的)

1>基本思想：

    将两个或两个以上的有序序列合并成一个新的有序序列：

有序序列v[1],v[2]...v[m]和v[m+1],...v[n] ====> v[1]...v[n] 这种归并方法称为2路归并。将多个有序序列归并为一个新的有序序列，称为多路归并。

检测两个有序序列A和B，C为归并后的新的有序序列：

  =>当i和j都在两个序列内变化时，根据关键码的大小将较小的数据元素排放到新序列k所指位置中

  =>当i与j中有一个已经超出序列时，将另一个序列中的剩余部分照抄到新序列中。

2>代码实现：

/*******************MergeSort.c*****************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void println(int array[], int len)
{
    int i = 0;
    for(i=0; i<len;i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void Merge(int src[], int des[],int low,int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int k = low;
    while( (i <= mid) && ( j <= high) )
    {
        if(src[i] < src[j])
        {
            des[k++] = src[i++];
        }
        else
        {
            des[k++] = src[j++];
        }
    }
    while( i<= mid )
    {
        des[k++] = src[i++];
    }
    while( j<= high)
    {
        des[k++] = src[j++];
    }
}

void MSort(int src[], int des[], int low, int high,int max)
{
    if( low == high)
    {
    des[low] = src[low];
    }
    else
    {
        int mid = (low + high) / 2;
        int* space = (int*)malloc(sizeof(int*)*max);
        if( space != NULL )
        {
            MSort(src,space,low,mid,max);
            MSort(src,space,mid+1,high,max);
            Merge(space,des,low,mid,high);
        }
        free(space);
    }
}

void MergeSort(int array[], int len) //O(n*logn)
{
    MSort(array,array,0,len-1,len);
}

int main(int argc, char *argv[])
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    println(array,len);
    MergeSort(array,len);
    println(array,len);
    return 0;
}

希尔排序，快速排序和归并排序将排序算法的时间复杂度提高到了O(n*logn)，希尔排序和快速排序是不稳定的，归并排序的排序结果是稳定的。