各种排序算法总结

排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今天,来总结下各种排序算法。

下面这个表格总结了各种排序算法的复杂度与稳定性:

各种排序算法复杂度比较.png

冒泡排序

冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好。

  • 算法原理

相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小的数就被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成

  • c++代码实现

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

选择排序

  • 算法原理

先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  • c++代码实现

void select_sort(int arr[], int len) { for (int i = 0; i < len; i++) { int index = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[index]) index = j; } if (index != i) { int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } }

插入排序

  • 算法原理

将数据分为两部分,有序部分与无序部分,一开始有序部分包含第1个元素,依次将无序的元素插入到有序部分,直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等,这里只讨论直接插入排序。它是稳定的排序算法,时间复杂度为O(n^2)

  • c++代码实现

void insert_sort(int arr[], int len) { for (int i = 1; i < len; i ++) { int j = i - 1; int k = arr[i]; while (j > -1 && k < arr[j] ) { arr[j + 1] = arr[j]; j --; } arr[j + 1] = k; } }

快速排序

  • 算法原理

快速排序是目前在实践中非常高效的一种排序算法,它不是稳定的排序算法,平均时间复杂度为O(nlogn),最差情况下复杂度为O(n^2)。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

  • c++代码实现

void quick_sort(int arr[], int left, int right) { if (left < right) { int i = left, j = right, target = arr[left]; while (i < j) { while (i < j && arr[j] > target) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] < target) i++; if (i < j) arr[j] = arr[i]; } arr[i] = target; quick_sort(arr, left, i - 1); quick_sort(arr, i + 1, right); } }

归并排序

  • 算法原理

归并排序具体工作原理如下(假设序列共有n个元素):

  • 将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素
  • 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  • 重复步骤2,直到所有元素排序完毕
  • 归并排序是稳定的排序算法,其时间复杂度为O(nlogn),如果是使用链表的实现的话,空间复杂度可以达到O(1),但如果是使用数组来存储数据的话,在归并的过程中,需要临时空间来存储归并好的数据,所以空间复杂度为O(n)

  • c++代码实现

void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index) { int i = start_index, j = mid_index + 1; int k = 0; while (i < mid_index + 1 && j < end_index + 1) { if (arr[i] > arr[j]) temp_arr[k++] = arr[j++]; else temp_arr[k++] = arr[i++]; } while (i < mid_index + 1) { temp_arr[k++] = arr[i++]; } while (j < end_index + 1) temp_arr[k++] = arr[j++]; for (i = 0, j = start_index; j < end_index + 1; i ++, j ++) arr[j] = temp_arr[i]; } void merge_sort(int arr[], int temp_arr[], int start_index, int end_index) { if (start_index < end_index) { int mid_index = (start_index + end_index) / 2; merge_sort(arr, temp_arr, start_index, mid_index); merge_sort(arr, temp_arr, mid_index + 1, end_index); merge(arr, temp_arr, start_index, mid_index, end_index); } }

堆排序

二叉堆

二叉堆是完全二叉树或者近似完全二叉树,满足两个特性

  • 父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值
  • 每个结点的左子树和右子树都是一个二叉堆

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。

堆的存储

一般都是数组来存储堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。存储结构如图所示:

堆结构.png

堆排序原理

  • 堆排序的时间复杂度为O(nlogn)
    • 算法原理(以最大堆为例)
    • 先将初始数据R[1..n]建成一个最大堆,此堆为初始的无序区
    • 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
    • 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
    • 重复2、3步骤,直到无序区只有一个元素为止。
  • c++代码实现

/** * 将数组arr构建大根堆 * @param arr 待调整的数组 * @param i 待调整的数组元素的下标 * @param len 数组的长度 */ void heap_adjust(int arr[], int i, int len) { int child; int temp; for (; 2 * i + 1 < len; i = child) { child = 2 * i + 1; // 子结点的位置 = 2 * 父结点的位置 + 1 // 得到子结点中键值较大的结点 if (child < len - 1 && arr[child + 1] > arr[child]) child ++; // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点 if (arr[i] < arr[child]) { temp = arr[i]; arr[i] = arr[child]; arr[child] = temp; } else break; } } /** * 堆排序算法 */ void heap_sort(int arr[], int len) { int i; // 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素 for (int i = len / 2 - 1; i >= 0; i--) { heap_adjust(arr, i, len); } for (i = len - 1; i > 0; i--) { // 将第1个元素与当前最后一个元素交换,保证当前的最后一个位置的元素都是现在的这个序列中最大的 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值 heap_adjust(arr, 0, i); } }

原文发布于微信公众号 - 交互设计前端开发与后端程序设计(interaction_Designer)

原文发表时间:2016-05-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏于晓飞的专栏

DualPivotQuickSort 双轴快速排序 源码 笔记

这个算法是Arrays.java中给基本类型的数据排序使用的具体实现。它针对每种基本类型都做了实现,实现的方式有稍微的差异,但是思路都是相同的,所以这里只挑了i...

1042
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

872
来自专栏chenjx85的技术专栏

leetcode-628-Maximum Product of Three Numbers

1594
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

632
来自专栏chenjx85的技术专栏

leetcode-605-Can Place Flowers

1043
来自专栏JavaEdge

2018-09-04Q:求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。方法一:递归实现1+2+..+n;

共同点:一,利用利用短路 && 来实现 if的功能;二,利用递归来实现循环while的功能

1002
来自专栏后端技术探索

是时候来彻底了解字符编码了!!

你是否认为“ASCII码 = 一个字符就是8比特”?你是否认为一个字节就是一个字符,一个字符就是8比特?你是否还认为你是否还认为UTF-8就是用8比特表示一个字...

912
来自专栏java思维导图

【一分钟知识】面对对象、基本类型

【一分钟回顾】系列 很多知识都是概念性的东西,有时候你知道这个技术的用法,但未必就能准确地说出它代表的含义与思想。一分钟回顾系列文章会从基础开始到后期的高级,带...

2945
来自专栏趣谈编程

堆排序

面试官:写一个堆排吧 我心想:幸好昨天刚看 ? 堆排是基于堆的一种排序算法,对于堆的了解,请看可以管理时间的二叉堆(如果对堆的插入和删除不清楚,强烈建议先看堆...

2309
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

2396

扫码关注云+社区

领取腾讯云代金券