常用十大排序算法

排序算法（十大排序）

排序算法是《数据结构与算法》中最基本的算法之一。

​ 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

一、冒泡排序

​ 冒泡排序（Bubble Sort）也是一种简单直观的排序算法。假设长度为n的数组arr，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值。接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。

冒泡排序算法的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   

算法的时间复杂度为O(n^2)。核心代码如下：

/* 冒泡排序 */
void BubbleSort(int arr[], int length) // arr： 需要排序的数组； length： 数组长度 注： int cnt = sizeof(a) / sizeof(a[0]);获取数组长度
{ 
   
	for (int i = 0; i < length; i++)
	{ 
   
		for (int j = 0; j < length -  i - 1; j++)
		{ 
   
			if (arr[j] > arr[j + 1])
			{ 
   
				int temp;
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

算法的时间复杂度为O(n^2)。完整代码如下： 注：下面的算法完整可以参考这个，下面就不写出完整代码了，都一样，就核心代码不一致

#include <stdio.h>
#define ARR_LEN 255 /*数组长度上限*/
#define elemType int /*元素类型*/
 
/* 冒泡排序 */
/* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */
/* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
/* arr[]: 排序目标数组; int length: 元素个数 */
void BubbleSort(int arr[], int length) 
{ 
   
	for (int i = 0; i < length; i++)
	{ 
   
		for (int j = 0; j < length -  i - 1; j++)
		{ 
   
			if (arr[j] > arr[j + 1])
			{ 
   
				int temp;
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}
 
int main (void) { 
   
    elemType arr[ARR_LEN] = { 
   3,5,1,-7,4,9,-6,8,10,4};
    int len = 10; 
    // int len = sizeof(arr) / sizeof(arr[0]); 获取数据长度
    int i;
     
    BubbleSort(arr, len);
    for (i=0; i<len; i++)
        printf ("%d\t", arr[i]);
    putchar ('\n');
     
    return 0;
}

二、选择排序

​ 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。具体来说，假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])，则将最小值min1和arr[0]交换，接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，依次类推，直到数组arr有序排列。算法的时间复杂度为O(n^2)。

选择排序算法的原理如下：

​ 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

​ 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

​ 3.重复第二步，直到所有元素均排序完毕。

核心代码如下：

// 自定义方法：交换两个变量的值
void swap(int *a,int *b) 
{ 
   
    int temp = *a;
    *a = *b;
    *b = temp;
}
/* 选择排序 */
void selection_sort(int arr[], int len)
{ 
   
    int i,j;
    for (i = 0 ; i < len - 1 ; i++) { 
   
        int min = i;
        for (j = i + 1; j < len; j++) { 
       // 遍历未排序的元素
            if (arr[j] < arr[min]) { 
     // 找到目前最小值
                min = j;   // 记录最小值
            }
        }
        swap(&arr[min], &arr[i]);    //做交换
        /*if (index != i) // 不用自定义函数时可以用选择下面方式进行交换 { temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; }*/

    }
}

三、插入排序

​ 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。例如要将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列，将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。

插入排序算法的原理如下：

​ 1.从第一个元素开始，该元素可以认为已经被排序；

​ 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

​ 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

​ 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

​ 5.将新元素插入到该位置后；

​ 6.重复步骤2~5。

核心代码如下：

/* 插入排序 */
void insertion_sort(int arr[], int len){ 
   
    int i,j,key;
    for (i=1;i<len;i++){ 
   
        key = arr[i];
        j=i-1;
        while((j>=0) && (arr[j]>key)) { 
   
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

四、希尔排序

​ 希尔排序(Shell’s Sort)在插入排序算法的基础上进行了改进，算法的时间复杂度与前面几种算法相比有较大的改进，但希尔排序是非稳定排序算法。其算法的基本思想是：先将待排记录序列分割成为若干子序列分别进行插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。该算法时间复杂度为O(n log n)。

希尔排序算法的原理如下：

​ 1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

​ 2.按增量序列个数 k，对序列进行 k 趟排序；

​ 3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

核心代码如下：

void shell_sort(int arr[], int len) { 
   
    int increasement = len;
	int i, j, k;
	do
	{ 
   
		// 确定分组的增量
		increasement = increasement / 3 + 1;
		for (i = 0; i < increasement; i++)
		{ 
   
			for (j = i + increasement; j < len; j += increasement)
			{ 
   
				if (arr[j] < arr[j - increasement])
				{ 
   
					int temp = arr[j];
					for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
					{ 
   
						arr[k + increasement] = arr[k];
					}
					arr[k + increasement] = temp;
				}
			}
		}
	} while (increasement > 1);
}

五、归并排序

​ 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。代价是需要额外的内存空间。若将两个有序表合并成一个有序表，称为2-路归并。 该算法时间复杂度为O(n log n)。

希尔排序算法的原理如下：

​ 1.把长度为n的输入序列分成两个长度为n/2的子序列；

​ 2.对这两个子序列分别采用归并排序；

​ 3.将两个排序好的子序列合并成一个最终的排序序列。

核心代码如下：

// 归并排序
void MergeSort(int arr[], int start, int end, int * temp) // start和end分别是左边界和右边界
{ 
   
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	MergeSort(arr, start, mid, temp);
	MergeSort(arr, mid + 1, end, temp);
 
	// 合并两个有序序列
	int length = 0; // 表示辅助空间有多少个元素
	int i_start = start;
	int i_end = mid;
	int j_start = mid + 1;
	int j_end = end;
	while (i_start <= i_end && j_start <= j_end)
	{ 
   
		if (arr[i_start] < arr[j_start])
		{ 
   
			temp[length] = arr[i_start]; 
			length++;
			i_start++;
		}
		else
		{ 
   
			temp[length] = arr[j_start];
			length++;
			j_start++;
		}
	}
	while (i_start <= i_end)  // 把剩下数的合并
	{ 
   
		temp[length] = arr[i_start];
		i_start++;
		length++;
	}
	while (j_start <= j_end)
	{ 
   
		temp[length] = arr[j_start];
		length++;
		j_start++;
	}
	// 把辅助空间的数据放到原空间
	for (int i = 0; i < length; i++)
	{ 
   
		arr[start + i] = temp[i];
	}
}

六、快速排序

​ 快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。一趟快速排序的具体过程可描述为：从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值，然后将记录中关键字比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。它是处理大数据最快的排序算法之一了。该算法时间复杂度为O(n log n)。

快速排序算法的原理如下：

​ 1.从数列中挑出一个元素，称为 “基准”（pivot）;

​ 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

​ 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

核心代码如下：

// 快速排序
void QuickSort(int arr[], int start, int end)
{ 
   
	if (start >= end)
		return;
	int i = start;
	int j = end;
	// 基准数
	int baseval = arr[start];
	while (i < j)
	{ 
   
		// 从右向左找比基准数小的数
		while (i < j && arr[j] >= baseval)
		{ 
   
			j--;
		}
		if (i < j)
		{ 
   
			arr[i] = arr[j];
			i++;
		}
		// 从左向右找比基准数大的数
		while (i < j && arr[i] < baseval)
		{ 
   
			i++;
		}
		if (i < j)
		{ 
   
			arr[j] = arr[i];
			j--;
		}
	}
	// 把基准数放到i的位置
	arr[i] = baseval;
	// 递归
	QuickSort(arr, start, i - 1);
	QuickSort(arr, i + 1, end);
}

七、堆排序

​ 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。该算法时间复杂度为O(n log n)。

堆排序算法的原理如下：

​ 1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

​ 2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

​ 3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

代码如下：

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

void swap(int *a, int *b) { 
   
    int temp = *b;
    *b = *a;
    *a = temp;
}

void max_heapify(int arr[], int start, int end) { 
   
    // 建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { 
    // 若子节点指标在范围內才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数 
            return;
        else { 
    // 否则交换父子內容再继续子节点和父节点比较
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) { 
   
    int i;
    // 初始化，i从最后一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) { 
   
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() { 
   
    int arr[] = { 
    3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

八、计数排序

​ 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序不是基于比较的排序算法。而是 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。该算法时间复杂度为O(n+k)。

计数排序算法的原理如下：

​ 1.找出待排序的数组中最大和最小的元素；

​ 2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

​ 3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

​ 4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

代码如下：

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

void print_arr(int *arr, int n) { 
   
        int i;
        printf("%d", arr[0]);
        for (i = 1; i < n; i++)
                printf(" %d", arr[i]);
        printf("\n");
}

void counting_sort(int *ini_arr, int *sorted_arr, int n) { 
   
        int *count_arr = (int *) malloc(sizeof(int) * 100);
        int i, j, k;
        for (k = 0; k < 100; k++)
                count_arr[k] = 0;
        for (i = 0; i < n; i++)
                count_arr[ini_arr[i]]++;
        for (k = 1; k < 100; k++)
                count_arr[k] += count_arr[k - 1];
        for (j = n; j > 0; j--)
                sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
        free(count_arr);
}

int main(int argc, char **argv) { 
   
        int n = 10;
        int i;
        int *arr = (int *) malloc(sizeof(int) * n);
        int *sorted_arr = (int *) malloc(sizeof(int) * n);
        srand(time(0));
        for (i = 0; i < n; i++)
                arr[i] = rand() % 100;
        printf("ini_array: ");
        print_arr(arr, n);
        counting_sort(arr, sorted_arr, n);
        printf("sorted_array: ");
        print_arr(sorted_arr, n);
        free(arr);
        free(sorted_arr);
        return 0;
}

九、桶排序

​ 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。该算法时间复杂度为O(n+k)。

桶排序算法的原理如下：

​ 1.设置一个定量的数组当作空桶；

​ 2.遍历输入数据，并且把数据一个一个放到对应的桶里去；

​ 3.对每个不是空的桶进行排序；

​ 4.从不是空的桶里把排好序的数据拼接起来。

代码如下：

#include<stdio.h>
int main() { 
   
     int book[1001],i,j,t;
     //初始化桶数组
     for(i=0;i<=1000;i++) { 
   
       book[i] = 0;
     }
     //输入一个数n，表示接下来有n个数
     scanf("%d",&n);
     for(i = 1;i<=n;i++) { 
   
       //把每一个数读到变量中去
       scanf("%d",&t);
       //计数 
       book[t]++;
     }
     //从大到小输出
     for(i = 1000;i>=0;i--) { 
   
       for(j=1;j<=book[i];j++) { 
   
         printf("%d",i);
       }
     }
    getchar();getchar();
    //getchar()用来暂停程序，以便查看程序输出的内容
    //也可以用system("pause");来代替
    return 0;
}

十、基数排序

​ 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。该算法时间复杂度为O(n+k)。

基数排序算法的原理如下：

​ 1.取得数组中的最大数，并取得位数；

​ 2.arr为原始数组，从最低位开始取每个位组成radix数组；

​ 3.对radix进行计数排序（利用计数排序适用于小范围数的特点）。

代码如下：

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

/* 基数排序 * 1.求出数组中最大的元素 * 2.求出最大元素是几位数, 设为i位 * 3.对所有的数进行i轮排序. * 首先排个位, 然后是十位, 然后百位 * 4.每一轮的排位都需要分桶, 桶是有顺序的, * 然后把桶里的数按顺序放入原来的数组中. * 5.直到i轮排序结束后, 数组排序完成. */

/*获取数字的位数*/
int figure(int num)
{ 
   
    int count = 1;
    int temp = num / 10;

    while(temp != 0)
    { 
   
        count++;
        temp /= 10;
    }

    return count;
}

/*查询数组中的最大数*/
int max(int *a, int n)
{ 
   
    int max = a[0];
    int i;

    for(i=1; i<n; i++)
    { 
   
        if(a[i] > max)
        { 
   
            max = a[i];
        }
    }

    return max;
}

/*将数字分配到各自的桶中, 然后按照桶的顺序输出排序结果*/
void sort2(int *a, int n, int loop)
{ 
   
    int *buckets[10] = { 
   NULL};
    int c[10] = { 
   0};
    int d[10] = { 
   1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    int i, j, k;
    int row;
    int temp = d[loop-1];

    /*统计每个桶的元素个数*/
    for(i=0; i<n; i++)
    { 
   
        row = (a[i] / temp) % 10;

        c[row]++;
    }

    /*为每个桶分配空间*/
    for(i=0; i<10; i++)
    { 
   
        buckets[i] = (int *)malloc(c[i]*sizeof(int));
    }

    memset(c, 0x00, sizeof(c));

    /*将数组中的数据分配到桶中*/
    for(i=0; i<n; i++)
    { 
   
        row = (a[i] / temp) % 10;

        buckets[row][c[row]] = a[i];

        c[row]++;
    }

    k = 0;

    /*将桶中的数, 倒回到原有数组中*/
    for(i=0; i<10; i++)
    { 
   
        for(j=0; j<c[i]; j++)
        { 
   
            a[k] = buckets[i][j];
            k++;
        }
    }

    /*释放桶内存*/
    for(i=0; i<10; i++)
    { 
   
        free(buckets[i]);
        buckets[i] = NULL;
    }
}

/*基数排序*/
void sort3(int *a, int n)
{ 
   
    int m = max(a, n);
    int loop = figure(m);
    int i;

    for(i=1; i<=loop; i++)
    { 
   
        sort2(a, n, i);
    }
}

int main()
{ 
   
    int a[] = { 
   2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
    int *p = a;
    int size;
    int i;

    /*计算数组长度*/
    size = sizeof(a) / sizeof(int);

    /*基数排序*/
    sort3(p, size);

    /*打印排序后结果*/
    for(i=0; i<size; i++)
    { 
   
        printf("%d\n", a[i]);
    }

    return 0;
}