C++常用排序算法

算法概述

常见的排序算可以分为以下两类：

1. 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于时间复杂度不能突破nlogn，因此称为非线性时间比较类排序
2. 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下限，以线性时间运行，因此称为线性时间非比较类排序
   
   
   排序相关概念：
3. 稳定：如果a原本在b的前面，且a=b，排序之后a仍然在b的前面
4. 不稳定：如果a原本在b的前面，且a=b，排序之后可能出现在b的后面

一、快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序流程

1. 首先设定一个分界值，通过该分界值将数组分成左右两个部分
2. 将大于或等于分界值得数据集中到数组右边，小于分界值得数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成两部分，同样在左边放置较小值，右边放置较大值，右侧的数据数据也可以做类似的处理
4. 重复上述过程，可以看出，这是一个递归定义，通过递归将左侧部分排好序后，再递归排好右侧部分的顺序，当左右两侧部分数据排序完成后，整个数组的排序也就完成了。

C++语言

#include <iostream>

using namespace std;

void Qsort(int arr[], int low, int high){
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = arr[low];
    while (true)
    {
        /*从左向右找比key大的值*/
        while (arr[++i] < key)
        {
            if (i == high){
                break;
            }
        }
        /*从右向左找比key小的值*/
        while (arr[--j] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交换i,j对应的值*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /*中枢值与j对应值交换*/
    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;
    Qsort(arr, low, j - 1);
    Qsort(arr, j + 1, high);
}

int main()
{
    int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};

    Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/

    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        cout << a[i] << "";
    }

    return 0;
}

def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 递归入口及出口        
        mid = data[len(data)//2]  # 选取基准值，也可以选取第一个或最后一个元素        
        left, right = [], []  # 定义基准值左右两侧的列表        
        data.remove(mid)  # 从原始数组中移除基准值        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data

# 示例：
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

快速排序算法的思想很好理解，排序性能不错，但是代码不易实现，还需要进行递归

二、冒泡排序

它重复的走访过要排序的元素列，依次比较两个相邻元素，如果顺序错误，就将他们交换过来，走访元素的工作是重复的进行直到没有相邻元素需要交换，说明排序已完成

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法原理

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

def bubble_sort(nums):
    for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums) - i - 1):  # j为列表下标
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
# 输出：[8, 12, 19, 22, 32, 33, 45, 97]

#include <iostream>
using namespace std;
template<typename T>
//整数或浮点数皆可使用
void bubble_sort(T arr[], int len)
{
    int i, j;  T temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)     //如果反向排序，此处j可以等于i
        if (arr[j] > arr[j + 1])
        {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
}
int main()
{
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';

    cout << endl;

    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (int) sizeof(arrf) / sizeof(*arrf);
    bubble_sort(arrf, len);
    for (int i = 0; i < len; i++)
        cout << arrf[i] << ' ';

    return 0;
}

冒泡排序实现较为简单，但是性能一般，最差的时间复杂度为o(n²)

三、选择排序

选择排序是一种简单直观的排序算法，它的工作原理是：第一从待排序的数据元素中选出最小的一个元素，放在序列的起始位置，然后从剩余未排序元素中寻找到最小元素，然后放到已排序的序列的末尾，直到全部待排序的数据元素的个数为零，选择排序为不稳定排序。

#include<iostream>
#include<time.h>
#include<iomanip>
using namespace std;
const int N=10;
int main()
{
    int a[N],i,j,temp,b;
    srand(time(NULL));
    for(i=0;i<N;i++)
        a[i]=rand()%100;
    for(i=0;i<N;i++)
        cout<<setw(3)<<a[i];
    cout<<endl;
    for(i=0;i<N-1;i++)
    {
        temp=i;
        for(j=i+1;j<N;j++)
        {
            if(a[temp]>a[j])
                temp=j;
        }
        if(i!=temp)
        {
            b=a[temp];
            a[temp]=a[i];
            a[i]=b;
        }
    }
    for(i=0;i<N;i++)
        cout<<setw(3)<<a[i];
    cout<<endl;
}

def selection_sort(list2):
  for i in range(0, len (list2)-1):
    min_ = i
    for j in range(i + 1, len(list2)):
      if list2[j] < list2[min_]:
        min_ = j
    list2[i], list2[min_] = list2[min_], list2[i]  # swap

注意区分冒泡排序和选择排序的区别，冒泡排序是从头开始遍历与相邻元素的大小关系，两层循环遍历就可以实现排序，选择排序是每次记住最小值的位置，注意记住的是最小值的位置，然后放置在合适的位置

插入排序

插入排序是一种简单直观且稳定的排序算法，如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，从而得到一种新的排序算法——插入排序法
插入排序法的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。时间复杂度为O(n²)

现有一个无序数组，共7个数：89 45 54 29 90 34 68。

使用直接插入排序法，对这个数组进行升序排序。

89 45 54 29 90 34 68

45 89 54 29 90 34 68

45 54 89 29 90 34 68

29 45 54 89 90 34 68

29 45 54 89 90 34 68

29 34 45 54 89 90 68

29 34 45 54 68 89 90

C++
//插入排序
void InsertSort(int* h, size_t len)
{
    if(h==NULL) return;
    if(len<=1) return;

    int i,j;
    //i是次数，也即排好的个数;j是继续排
    for(i=1;i<len;++i)
        for(j=i;j>0;--j)
            if(h[j]<h[j-1]) Swap(h[j],h[j-1]);
            else break;

    return;
}

def insert_sort(lst):
    for i in range(1,len(lst)):
        tmp = lst[i]
        j = i - 1
        while j >= 0 and tmp < lst[j]:
            lst[j + 1] = lst[j]
            j = j - 1
        lst[j + 1] = tmp
    return lst

五、归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序，然后将其合并成一个有序列。归并排序是一种稳定的排序方法。

归并排序强调“分”和“治”，分就是将一个数列划分成尽可能小的子序列，治就是将子序列排序然后合并成一个有序列

对于治的最后一步如果我们要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

上图的思想就是利用两个指针或者计数器，分别记录两个子序列的位置，从头开始进行比较，因为子序列已经是有序列了，只需要比较两个子序列的大小，进行最后一次排序即可。

python
def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result
print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])

C/C++不易实现，代码量过大，需要递归实现

六、希尔排序

希尔排序是插入排序的一种改进版，又称“缩小增量排序”，希尔排序为非稳定算法，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词（数字）越来越多，当增量减至1时，整个序列恰被分成一组，算法终止。

如图，最初我门可以将增量gap=length/2，缩小增量继续以gap=gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

//希尔排序
void ShellSort(int* h, size_t len)
{
    if(h==NULL) return;
    if(len<=1) return;

    for(int div=len/2;div>=1;div/=2)
        for(int k=0;k<div;++k)
            for(int i=div+k;i<len;i+=div)
                for(int j=i;j>k;j-=div)
                    if(h[j]<h[j-div]) Swap(h[j],h[j-div]);
                    else break;

    return;
}

七、堆排序

堆排序实际上是利用堆的性质来进行排序的

堆得定义：
堆实际上是一颗完全二叉树
完全二叉树：
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

1. 所有的叶节点都出现在第K层或K-1层
2. 对任一节点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1层

堆满足两个性质：
1.堆的每一个父节点都大于或小于其子节点
2.堆的每个左子树和右子树也是一个堆

堆的分类：
1.最大堆（大顶堆）：堆的每个父节点都大于其孩子节点
2.最小堆（小顶堆）：堆的每个父节点都小于其孩子节点

堆的存储：
一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如下图所示：

堆排序：由上面的介绍我们可以看出堆的第一个元素要么是最大值（大顶堆），要么是最小值（小顶堆），这样在排序的时候（假设共n个节点），直接将第一个元素和最后一个元素进行交换，然后从第一个元素开始进行向下调整至第n-1个元素，所以，如果需要升序，就要建立一个大顶堆，降序就要建立一个小顶堆。

堆排序的三个步骤：
1.建堆
2.交换数据
3.向下调整

假设我们现在要对数组arr[]={8,5,0,3,7,1,2}进行排序（降序）：
首先要先建小堆：

堆建好了下来就要开始排序了：