排序算法

1 排序算法概述

常见排序算法比较

1.1 插入排序

介绍：

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据序列.
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

特点：
1、算法适用于少量数据的排序，
2、最优时间复杂度为O(n^2)，当输入数组就是排好序的时候，复杂度为O(n)。
3、是稳定的排序方法。

包括：
直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。

步骤：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5

代码：

void insert_sort(int*array,unsignedintn)
{
    inti,j;
    inttemp;
    for(i=1;i<n;i++)
    {
       temp=*(array+i);
       for(j=i;j>0&&*(array+j-1)>temp;j--)
       {
           *(array+j)=*(array+j-1);
       }
       *(array+j)=temp;
   }
}

直接插入排序
其实插入排序的复杂度和逆序对的个数一样，当数组倒序时，逆序对的个数为n(n-1)/2，因此插入排序复杂度为O(n^2)。
在算法导论2-4中有关于逆序对的介绍。

1.2 冒泡排序

介绍：

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码示例：

#include <stdio.h>
#define SIZE 8

void bubble_sort(**int** a[], **int** n);

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

int main()
{
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    int i;
    bubble_sort(number, SIZE);
    for (i = 0; i < SIZE; i++)
    {
        printf("%d", number[i]);
    }
    printf("\n");
}

1.3 选择排序

介绍：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

其实就是每次选择当前数组里面最小的数，然后与当前数组的第一个数字交换位置

步骤：
1.遍历数组查找当前数组被排序数字里面最小的数
2.将查找出来的最小的数与当前数组被排序数字中的第一个数字交换位置
3.对不包含已经排好序的数字(也就是去掉刚刚移到序号小的位置的数字)，重复步骤1-2，直至遍历到最后一个数字

代码示例：

/* 版本二 */
#include <stdio.h>
#include <math.h>

#define MAX_SIZE 101
#define SWAP(x, y, t)  ((t) = (x), (x) = (y), (y) = (t))

void sort(int[], int);      /* selection sort */

voidmain(**void**)
{
    int i, n;
    int list[MAX_SIZE];
    printf("Enter the number of numbers to generate: ");
    scanf_s("%d", &n);
    if (n < 1 || n > MAX_SIZE){
        fprintf(stderr, "Improper value of n\n");
        exit(1);
    }
    for (i = 0; i < n; i++){    /* randomly generate numbers */
        list[i] = rand(1000);
        printf("%d ", list[i]);
    }
    sort(list, n);
    printf("\n Sorted array:\n");
    for (i = 0; i < n; i++)    /* print out sorted numbers */
        printf("%d ", list[i]);
    printf(("\n");
}


void sort(**int** list[], **int** n)
{
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++){
        min = i;
        for (j = i + 1; j < n; j++)
        if (list[j] < list[min])
            min = j;
        SWAP(list[i], list[min], temp);
    }
 }

1.4 归并排序

1.5 快速排序

1.6 堆排序

1.7 计数排序

1.8 基数排序

1.9 桶排序

3 算法的选择