常见八大排序算法总结（包含基本原理以及代码实现）_顺序表基准排序

目录

1.冒泡排序 

2.插入排序

3.希尔排序

4.堆排序

5.归并排序

6.快速排序

7.表排序

8.基数排序

---

排序的概念：排序是指按关键字的非递减或非递增顺序对一组记录重新进行排序的操作。

1.冒泡排序 

（1）算法思想：

首先两两比较相邻元素A(I)和A(I+1)(I=1,2,…N-1),如果A(I)>A(I+1),则交换A(I)和A(I+1)的位置，

然后对剩下的N-1个元素，再两两进行比较，按同样规则交换它们的位置,经过N-2次比较,将次最大值交换到A(N-1)的位置;

如法炮制,经过N-1趟的“冒泡处理”,每趟进行N-i次的比较,全部数列有序。
（2）代码实现

#include<iostream> 
#include<cmath>
using namespace std; //指定名字空间
int main() 
{
    int a[100]; //定义数组，大小100
    int N; //元素的实际个数
    int i = 0, j = 0; //循环变量，并进行初始化
    cin >> N; //输入元素个数
              //-------输入数据-----------
    for (i = 0; i<N; i++) //输入N个元素
        cin >> a[i]; //循环体只有一行
                     //-------排序---------------
    for (i = 0; i<N - 1; i++) { //控制n-1趟冒泡
        for (j = 0; j<N - 1 - i; j++)
        {
            if (a[j]>a[j + 1]) { //比较相邻的两个元素
                int tmp; //临时变量
                tmp = a[j]; //交换
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
    //--------输出----------
    for (i = 0; i<N; i++) 
    { //使用循环，输出N个元素
        cout << a[i] << " "; //输出a[i], 后加空格，不换行
    }
    cout << endl; //所有元素输出完之后才换行
    return 0; //函数返回
}

2.插入排序

2.1直接插入排序

（1）直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表。

（2）代码实现

void InsertSort(Sqlist &L)//对顺序表L进行直接插入排序
 
{
 
for(int i=2;i<=L.length;i++)
 
if(L.r[i].key<L.r[i-1].key)
 
{
L.r[0]=L.r[i];//将待插入的记录暂时存到监事哨中
 
L.r[i]=L.r[i-1];
 
for(int j=i-2;L.r[0].key<L.r[j].key;--j)
 
{
L.r[j+1]=L.r[j];//记录逐个后移，直到找到插入位置
 
}
 
L.r[j+1]=L.r[0];
 
}
 
}

2.2折半插入排序

（1）折半插入排序在“查找”操作中可利用“折半查找”来实现。

（2）代码实现

void BInsertSort(Sqlist &L)
 
{//对顺序表L进行折半插入
 
for(int i=2;i<=L.length;i++)
 
{
L.[0]=L.r[i];
 
low=1; high=i-1;//设置区间初值
 
while(low<=high){
m=(low+high)/2;//折半
 
if(L.r[0].key<L.r[m].key)
 
high=m-1;//插入点在前一子表
 
else
 
low=m+1; //插入点在后一子表
 
}
 
for(j=i-1;j>=high+1;j--)
 
L.r[j+1]=L.r[j];//记录后移
 
L.r[high+1]=L.r[0];
 
}
 
}

3.希尔排序

（1）希尔排序又称“缩小增量排序”，是插入排序的一种

（2）代码实现

void ShellInsert(Sqlist &L,int dk)
 
{//对顺序表L做一趟增量是dk的希尔插入排序
 
for(int i=dk+1;i<L.length;i++)
 
{
if(L.r[i].key<L.r[i-dk].key)
 
{
L.r[0]=L.r[i];
 
for(int j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
 
L.r[j+dk]=L.r[j];//记录后移，直到找到插入位置
 
L.r[j+dk]=L.r[0];
 
}
 
}
 
void SheelSort(Sqlist &L,int dt[],int t)
 
{//按增量序列dt[0.t-1]对顺序表L做t趟希尔排序
 
for(int k=0;k<t;k++)
 
{
ShellInsert(L,dt[k]);
 
}
 
}

4.堆排序

（1）堆排序是一种树形选择排序，在排序过程中，将待排序的记录r[1..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择最大关键字（或最小）的记录。

（2）代码实现

void HeapSort(Sqlist &L)
 
{
//对顺序表L进行堆排序
 
CreatHeap(L);//把无序序列L.r[1..L.length]建成大根堆
 
for(int i=L.length;i>1;i--)
 
{
x=L.r[1];//将堆记录和当前未经排序子序列L.r[1..i]中最后一个记录互换
 
L.r[1]=L.r[i];
 
L.[i]=x;
 
HeapAdjust(L,1,i-1);//将L.r[1...i-1]重新调整为大根堆
 
}
 
}

5.归并排序

（1）归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。

（2）代码实现

void Msort(RedType R[],ReadTye T[],int low,int high)
 
{
//R[low..high]归并排序后放入T[low..high]中
 
if(low==high) T[low]=R[low];
 
else {
mid=(low+high)/2;//将当前序列一分为二，求出分裂点mid
 
MSort(R,S,low,mid);//对于序列R[low..mid]递归并排序，结果放入S[low,high]
 
Msort(R,S,mid+1,high);//对于序列R[mid+1,high]递归排序，结果放入S[mid+1,high]
 
Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..high]归并到T[low..high]
 
}
 
}
 
void MergeSort(Sqlist &L)
 
{
//对顺序表L进行归并排序
 
MSort(L.r,L.r,1,L.length);
 
}

6.快速排序

（1）快速排序使用分而治之来把一个串分为两个子串。具体算法描述如下：
步骤1：从数列中挑出一个元素，称为 “主元”（pivot ）；
步骤2：重新排序数列，所有元素比主元值小的摆放在主元前面，所有元素比主元值大的摆在主元的后面（相同的数可以到任一边）。在这个分区退出之后，该主元就处于数列的中间位置。这个称为分区（partition）操作；
步骤3：递归地（recursive）把小于主元值元素的子数列和大于主元值元素的子数列排序。

（2）如何选主元：

法一：随机去主元pivot,但是rand()函数不便宜

法二：取头、中、尾的中位数，例如8、12、3的中位数就是8

（3）子集划分

以主元为基准，划分为两部分。

（4）快速排序的问题：用递归，对于小规模的数据（例如N不到100）可能还不如插入排序快

解决方案：当递归的数据规模充分小，则停止递归，直接调用简单排序、在程序中定义一个cutoff的阙值

（5）代码实现

void Quicksort(ElementType A[ ],int Left,int Right)
 
{if(Cutoff<=Right-Left){
 
Pivot=Median3(A,Left,Right);//调用Median3函数选取主元
 
i=Left; j=Right-1;
 
for( ; ; ){
 
while(A[++i]<Pivot){ }
 
while(A[--j]>Pivot) { }
 
if(i<j)
 
Swap(&A[i],&A[j]);
 
else break;
 
}
 
Swap(&A[i],&A[Right-1]);  
 
Quicksort(A,Left,i-1);//边部分递归调用快速排序算法
 
Quicksort(A,i+1,Right);//右边部分递归调用快速排序算法
 
}
 
else 
 
Insertion_Sort(A+Left,Right-Left+1);//否则，采用插入排序

7.表排序

（1）表排序当待排数组中的元素不是简简单单的整数，而是复杂的结构体，那么移动元素所花费的时间就不能忽略不计了，这时候我们要减少元素之间移动的次数了。表排序就是这么一个排序，在表排序的过程中，实际上是不需要移动元数的，我们要移动的是指向这些元素的指针。（在数组中及指向该数据的数组下标）。

（2）代码实现

/* 表排序 */
void TableSort(ListElementType *A, int Size)
{
    int *Table = NULL;
    ListElementType TempA;
    int i = 0, j = 0, Temp = 0;
 
    /* 申请Table空间 */
    Table = (int *)malloc(sizeof(int)*Size);
 
    /* 初始化Table */
    for (i = 0; i < Size; i++)
    {
        Table[i] = i;
    }
 
    /* 给Table排序（任何排序方法都可以） */
    for (i = 1; i < Size; i++)
    {
        Temp = Table[i];
        for (j = i; j > 0 && A[Temp] < A[Table[j-1]]; j--)
        {
            Table[j] = Table[j - 1];
        }
        Table[j] = Temp;
    }
 
    /* 给数组排序 */
    for (i = 0; i < Size; i++)
    {
        if (i != Table[i])
        {
            TempA = A[i];
            for (j = i; Table[Table[j]] != Table[j]; j = Temp)
            {
                Swap(&A[j], &A[Table[j]]);
                Temp = Table[j];
                Table[j] = j;
            }
            A[j] = TempA;
        }
    }
 
    /* 释放Table空间 */
    free(Table);
}

8.基数排序

（1）算法思想：

设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步：
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步：
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

（2）代码实现

/**
* name:基数排序
* time:15/8/16 15:00
* environment: ubuntu 14.04， sublime text 3
*/
#include <iostream>
using namespace std;
 
/*
* 打印数组
*/
void printArray(int array[],int length)
{
    for (int i = 0; i < length; ++i)
    {
        cout << array[i] << " ";
    }
    cout << endl;
}
/*
*求数据的最大位数,决定排序次数
*/
int maxbit(int data[], int n) 
{
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int tmp[n];
    int count[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
}
 
int main()
{
    int array[10] = {73,22,93,43,55,14,28,65,39,81};
    radixsort(array,10);
    printArray(array,10);
    return 0;
}
 
//结果
//14 22 28 39 43 55 65 73 81 93  

补充 下表 各种内部排序方法的比较

 还有很多其他排序算法，需要不断学习。