一、前言
排序算法也是面试中常常提及的内容,问的最多的应该是快速排序、堆排序。这些排序算法很基础,但是如果平时不怎么写代码的话,面试的时候总会出现各种bug。虽然思想都知道,但是就是写不出来。本文打算对各种排序算法进行一个汇总,像插入排序、冒泡排序、选择排序等就简单的介绍,重点关注快速排序和堆排序。需要提到的一点就是:插入排序,冒泡排序,归并排序,计数排序都是稳定的排序,而其他排序则都是不稳定的。
二、简单排序
1)插入排序
插入排序是很基本的排序,特别是在数据基本有序的情况下,插入排序的性能很高,基本可以达到O(N)。当然其最坏情况和平均情况时间复杂度都是O(N^2)。代码如下:
void insert_sort(int x[], int n)
{
int i, j;
for (i=1; i<n; i++) {
/*循环不变式:x[0...i-1]有序。每次迭代开始前,x[0...i-1]有序, 循环结束后i=n,x[0...n-1]有序*/
int key = x[i];
for (j=i; j>0 && x[j-1]>key; j--) {
x[j] = x[j-1];
}
x[j] = key;
}
}
2)选择排序
选择排序的思想就是第i次选取第i小的元素放在位置i。比如第1次就选择最小的元素放在位置0,第2次选择第二小的元素放在位置1。选择排序最好和最坏时间复杂度都为O(N^2)。代码如下:
void select_sort(int x[], int n)
{
int i, j, min, tmp;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++) {
if (x[j] < x[min])
min = j;
}
if (min != i)
tmp = x[i], x[i] = x[min], x[min] = tmp;//交换x[i]和x[min]
}
}
循环不变式:在外层循环执行前,x[0...i-1]包含a中最小的i个数,且有序。
初始时,i=0,x[0...-1]为空,显然成立。
每次执行完成后,x[0...i]包含x中最小的i+1个数,且有序。即第一次执行完成后,x[0...0]包含x最小的1个数,且有序。
循环结束后,i=n-1,则x[0...n-2]包含x最小的n-1个数,且已经有序。所以整个数组有序。
3)冒泡排序
冒泡排序时间复杂度跟选择排序相同。其思想就是进行n-1趟排序,每次都是把最小的数上浮,像鱼冒泡一样。最坏情况为O(N^2)。代码如下:
void bubble_sort(int x[], int n)
{
int tmp;
for (int i=0; i<n; i++) {
for (int j = n-1; j>=i+1; j--) {
if (x[j] < x[j-1])
tmp = x[j], x[j] = x[j-1], x[j-1] = tmp;
}
}
}
循环不变式:在循环开始迭代前,子数组x[0...i-1]包含了数组x[0..n-1]的i-1个最小值,且是排好序的。
对冒泡排序的一个改进就是在每趟排序时判断是否发生交换,如果一次交换都没有发生,则数组已经有序,可以不用继续剩下的趟数直接退出。改进后代码如下:
void bubble_sort_better(int x[], int n)
{
int tmp;
for (int i=0; i<n; i++) {
int sorted = 1;
for (int j = n-1; j>=i+1; j--) {
if (x[j] < x[j-1]) {
tmp = x[j], x[j] = x[j-1], x[j-1] = tmp;
sorted = 0;
}
}
if (sorted)
return ;
}
}
4)计数排序
假定数组为A[0...n-1],数组中存在重复数字,数组中最大数字为k,建立两个辅助数组B和C,B用于存储排序后的结果,C用于存储临时值。时间复杂度为O(N),适用于数字范围较小的数组。具体见代码:
const int N = 5; //数字个数
int b[N+1];
void count_sort(int a[], int n, int k) //k为数组最大数字
{
int c[k+1]; //辅助数组
for (int i=0; i<=k; i++)
c[i] = 0;
for (int j=0; j<n; j++)
c[a[j]] = c[a[j]] + 1; //C[i]包含等于i的元素个数
for (int i=1; i<=k; i++)
c[i] = c[i] + c[i-1]; //C[i]包含小于等于i的元素个数
for (int j=n-1; j>=0; j--) {
b[c[a[j]]] = a[j]; //结果存在B[1...N]中
c[a[j]] = c[a[j]] - 1;
}
}
5)归并排序
归并排序通过分治算法,先排序好两个子数组,然后将两个子数组归并。时间复杂度为O(NlgN)。代码如下:
/*归并排序代码*/
void merge_sort(int a[], int p, int r)
{
if (p < r) {
int q = p+(r-p)/2;
merge_sort(a, p, q);
merge_sort(a, q + 1, r);
merge(a, p, q, r);
}
}
void merge(int a[], int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
int left[n1], right[n2];
int i, j;
for (i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i] = a[start + i];
for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j] = a[mid + 1 + j];
i = j = 0;
int k = start;
while (i < n1 && j < n2) {
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
}
while (i < n1) /* left[] is not exhausted */
a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
a[k++] = right[j++];
}
三、堆排序
分享到:
相关推荐
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档
排序算法排序算法排序算法排序算法排序算法排序算法排序算法
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将 给出详细的说明...
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
十种排序算法介绍十种排序算法介绍十种排序算法介绍
超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称...
最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
包括堆排序算法实现,直接插入排序算法实现和快速排序算法实现。