关键词：
1.冒泡排序
转自百度百科：
冒泡排序，这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
以下过程动图摘自依韵的博客：
/**
* 冒泡排序：每个元素跟剩下的元素相比，直到冒到剩下的最大
* 时间复杂度O（n^2);
* 空间复杂度 O(1);
* 是否稳定：
* @param array arr
* @returns
*/
const bubbleSort = function(arr)
let arrLen = arr.length;
for(let i = 0; i < arrLen; i++)
for(let j = 0 ; j < arrLen - i; j++)
// 相邻元素交换
if (arr[j] > arr[j+1])
// swap(arr[j], arr[j+1])
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
return arr;
console.time('bubble')
console.log(bubbleSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
console.timeEnd('bubble')2. 选择排序
/*
* @description: 选择排序，不断在剩余元素中选择最小/最大的元素
* 时间复杂度O（n^2);
* 空间复杂度 O(1);
* 是否稳定：
*/
const selectSort = function(arr)
let len = arr.length;
for(let i=0; i<len; i++)
let minNum = arr[i]
for(let j=i; j<len; j++)
if(minNum > arr[j])
// swap(minNum, arr[j])
let temp = minNum;
minNum = arr[j];
arr[j] = temp;
arr[i] = minNum
return arr;
console.log(selectSort([2,5,34,6,3]))3. 插入排序
/*
* @description: 每个元素插入前面已经拍好序的元素中合适的位置，其他元素依次移动; 适合基本有序队列的排序
* 时间复杂度O（n^2);
* 空间复杂度 O(1);
* 是否稳定：
*/
const insertSort = function(arr)
const n = arr.length;
for (let i=0; i<n; i++)
for (let j=i; j>0; j--)
if (arr[j] < arr[j-1])
// swap(arr[j], arr[j-1])
[arr[j], arr[j-1]] = [arr[j-1], arr[j]]
return arr;
console.time("time")
console.log(insertSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
console.timeEnd('time');4. 快速排序
/**
* 快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。
* 快速排序: 快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
* 1. 从数列中挑出一个元素，称为 "基准"（pivot）;
* 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
* 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
* 时间复杂度：O(nlogn)
* 空间复杂度：O(h)
* 是否稳定：不稳定
* @param * arr
*/
function quickSort(arr)
QSort(arr, 0, arr.length-1)
/**
* 快速排序函数
* @param * arr 待排序数组
* @param Number low 最小下标值
* @param Number high 最大下标值
*/
function QSort(arr, low, high)
let pivot = 0;
if (low < high)
// 获取基准值的下标
pivot = Partition(arr, low, high);
QSort(arr, low, pivot - 1);
QSort(arr, pivot + 1, high);
/**
* 切分函数：
* @param * arr
* @param Number low
* @param Number high
* @returns 基准值下标
*/
function Partition(arr, low, high)
// 子数组的第一个值作为基准值，存在性能陷阱(取到最小值，或者最大值)，理想情况是取到中间的数值
// let pivotkey = arr[low];
// or三数取中法获得基准点(效率好一点)
let m = low + (high - low) / 2;
if (arr[low] > arr[high])
swap(arr, low, high);
if (arr[m] > arr[high])
swap(arr, m, high)
if (arr[low] > arr[m])
swap(arr, low, m)
let pivotkey = arr[low];
// 大于基准点的放在右边，小于基准点的放在左边
while(low < high)
while(low < high && arr[high] >= pivotkey)
high--;
swap(arr, low, high)
while(low < high && arr[low] <= pivotkey)
low++
swap(arr, low, high)
return low;
/**
* 交换函数
*/
function swap(arr, a, b)
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
let arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.time("time")
quickSort(arr);
console.log(arr);
console.timeEnd('time');5. 堆排序
/**
* 堆排序
* 实际上是选择排序的一种，我们可以看到堆的结构是一个完全二叉树，采用一维数组存储
* 以大顶堆为例
* 性质：这里用到了完全二叉树性质，对于一个n个节点的完全二叉树的节点按层序变化，对任一节点i (1<=i<=n)。
* 1. 如果i = 1, 则节点 i 是二叉树的根，无双亲；如果 i>1 ,其双亲节点是Math.floor(i/2)，向下取整。
* 2. 如果 2i > n, 则节点无左孩子; 否则左孩子是节点 2i。
* 3. 如果 2i+1 > n, 则节点无右孩子，否则右孩子是节点 2i+1。
* 算法中之所以为Math.floor(n/2) - 1, 因其存储下标从0开始，
*/
function heapSort(arr)
/**
* 建堆
*/
const n = arr.length;
// 索引从0开始，最后一个非叶子节点Math.floor(n/2) - 1
for(let i = Math.floor(n/2) - 1; i >= 0; i--)
adjustHeap(arr, i, n);
// 堆排，每次选择堆顶元素 arr[0] (剩余最大元素)，与末尾元素 arr[i] 进行交换
for( let i = n - 1; i > 0; i--)
swap(arr, 0, i);
adjustHeap(arr, 0, i);
return arr;
/**
* 堆调整
* @param 待排序数组 arr
* @param 当前起始节点 i
* @param 堆的长度 n
*/
function adjustHeap(arr, i, n)
let leftChild = 2 * i + 1;
let rightChild = 2 * i + 2;
// 假设初始节点最大
let largeNode = i;
// 左节点存在 && 左节点大于初始节点
if ( leftChild < n && arr[leftChild] > arr[largeNode])
largeNode = leftChild;
// 右节点存在 && 右节点大于初始节点/左节点
if (rightChild < n && arr[rightChild] > arr[largeNode])
largeNode = rightChild;
if (largeNode !== i)
// 将最大的节点和初始节点调整位置
swap(arr, i, largeNode);
// 再往下继续调整
adjustHeap(arr, largeNode, n)
/**
* 交换元素
* @param arr
* @param 交换元素下标 a
* @param 交换元素下标 b
*/
function swap(arr, a, b)
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
console.log(heapSort([90,70,80,60,10,40,50,30,20]))
几种常见的排序算法分析学习
...入，二分插入，希尔，快速以及归并排序。同时还有Java实现代码，算法分析和示意图冒泡排序算法描述设待排序记录序列中的记录个数为n一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换... 查看详情
排序算法3种简单排序(选择，冒泡，插入)
...心的操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。本文简单温习下最基础的三类算法：选择，冒泡，插入。... 查看详情
常见的排序算法
插入排序直接插入排序，折半插入排序，2-路插入排序，希尔排序快速排序冒泡排序，快速排序（冒泡排序改进），选择排序简单选择排序，树形选择排序，堆排序归并排序基数排序 查看详情
排序算法之冒泡选择插入排序（java）(代码片段)
文章目录通过Java实现冒泡、选择、插入排序算法冒泡排序冒泡排序介绍和实现具体代码的实现选择排序选择排序介绍和实现选择排序图解具体代码实现插入排序插入排序介绍和实现插入排序图解具体代码实现通过Java实现冒泡、... 查看详情
java常见数据算法_插入排序
...素，在其前面的元素中找到适当的位置进行插入。其参考实现如下：packagecom.zcp.ch04;/**@authorAdministrator冒泡排序的实现*/publicclassInsertArray{//数组privatelong[]arr=null;//数组中有效数据的大小privateintelems;publicInsertArray(){arr=ne 查看详情
图解排序算法之3种简单排序(选择，冒泡，直接插入)
...心的操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。本文简单温习下最基础的三类算法：选择，冒泡，插入。... 查看详情
javascript新手学习笔记3——三种排序方式（冒泡排序插入排序快速排序）
...，当时学C语言的时候，卡在排序算法。今天来总结一下javascript中如何实现三种排序算法。1.冒泡排序（默认升序排列哦） 原理： 冒泡排序的原理，顾名思义，就是小数往上冒，大数往下沉。从第一个数开始，如果比第... 查看详情
常见排序算法介绍和实现(代码片段)
文章目录前言一、排序的概念及应用1.1排序的概念1.2排序算法的稳定性1.3外部排序和内部排序二，常见的排序算法2.1插入排序2.1.1插入排序基本思想2.1.2直接插入排序的特性2.1.3希尔排序2.2选择排序2.2.1基本思想：2.2.2直接... 查看详情
用javascript实现排序算法(代码片段)
用JavaScript实现排序算法冒泡排序选择排序插入排序冒泡排序冒泡排序就是重复从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置。JavaScript代码实现:代码简介：声明一个数组变量，通过while给... 查看详情
图解排序算法之3种简单排序(选择，冒泡，直接插入)(代码片段)
...心的操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。本文简单温习下最基础的三类算法：选择，冒泡，插入。... 查看详情
常见排序算法
...并排序。 冒泡排序：每一轮排序得出一个最大值1#for实现2lst=[7,9,3,11,45,23,12,87,234,12,5,93]3n=len(lst)45foriinrange(n-1):6flag=True7forjinrange(n-1-i):8iflst[j]>lst[j+1]:9lst[j],lst 查看详情
常见排序算法小结
排序算法有很多种，包括冒泡排序，选择排序，快速排序，插入排序，希尔排序，堆排序等。这里着重讨论下冒泡排序，快速排序和插入排序这三种排序算法。冒泡排序——时间复杂度O( n2 )冒泡排序从第一个元素开始，... 查看详情
算法之常见的排序算法
我们平时说的“排序”，指的是内部排序，即使用内存资源进行排序的。除了内部排序之外，还有外部排序。本文主要介绍内部排序。 内部排序分为插入排序、选择排序、交换排序、归并排序等。其中，插入排序又分为... 查看详情
图解排序算法之3种简单排序(选择，冒泡，直接插入)(代码片段)
...操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。本文简单温习下最基础的三类算法：选择，冒泡... 查看详情
java实现几种常见排序方法
日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。一、冒泡排序 冒泡排序是一种简单的排序算法。它重复地走访... 查看详情
排序算法python实现
参考技术A排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中... 查看详情
数据结构之八大排序算法(c语言实现)(代码片段)
...排序在现实生活中的应用常见的排序算法常见排序算法的实现直接插入排序希尔排序选择排序堆排序冒泡排序冒泡排序的优化快速排序Hoare法快速排序时间复杂度快速排序的优化挖坑法前后指针法快速排序非递归归并排序计数排... 查看详情
常见的排序算法
...不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：关于时间复杂度：平方阶(O(n2))排序各... 查看详情