关键词：
---恢复内容开始---
作者 ： liuyang0
来源 ： 博客园
常见排序算法总结与实现
本文使用Java实现这几种排序。
以下是对排序算法总体的介绍。
冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度：O(n^2)，最优时间复杂度：O(n)，平均时间复杂度：O(n^2)
1public static void bubbleSort(Comparable[] a)
2 int j, flag;
3 Comparable temp;
4 for (int i = 0; i < a.length; i++)
5 flag = 0;
6 for (j = 1; j < a.length - i; j++)
7 if (a[j].compareTo(a[j - 1]) < 0)
8 temp = a[j];
9 a[j] = a[j - 1];
10 a[j - 1] = temp;
11 flag = 1;
12
13
14 // 如果没有交换，代表已经排序完毕，直接返回
15 if (flag == 0)
16 return;
17
18
19
插入排序
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
时间复杂度：O(n^2)，最优时间复杂度：O(n),平均时间复杂度：O(n^2)
下面展示了三种插入排序的实现，第二种方法减少了交换次数，第三种采用二分查找法查到插入点。
1public static void insertionSort(Comparable[] a)
2 int length = a.length;
3 Comparable temp;
4 for (int i = 1; i < length; i++)
5 for (int j = i; j > 0 && a[j].compareTo(a[j - 1]) < 0; j--)
6 temp = a[j];
7 a[j] = a[j - 1];
8 a[j - 1] = temp;
9
10
11
12
13// 对实现Comparable的类型进行排序，先将大的元素都向右移动，减少一半交换次数
14public static void insertionSort(Comparable[] a)
15 int length = a.length;
16 Comparable temp;
17 int j;
18 for (int i = 1; i < length; i++)
19 temp = a[i];
20 for (j = i; j > 0 && temp.compareTo(a[j - 1]) < 0; j--)
21 a[j] = a[j - 1];
22
23 a[j] = temp;
24
25
26
27// 二分插入排序，使用二分查找找到插入点，然后进行移位
28public static void insertionSort(Comparable[] a)
29 int length = a.length;
30 Comparable temp;
31 int j;
32 for (int i = 1; i < length; i++)
33 if (a[i].compareTo(a[i - 1]) < 0)
34 temp = a[i];
35 int index = binarySearch(a, a[i], 0, i - 1);
36 for (j = i - 1; j >= index; j--)
37 a[j + 1] = a[j];
38
39 a[index] = temp;
40
41
42
43
44private static int binarySearch(Comparable[] a, Comparable target, int start, int end)
45 int mid;
46 while (start <= end)
47 mid = (start + end) >> 1;
48 if (target.compareTo(a[mid]) < 0)
49 end = mid - 1;
50 else
51 start = mid + 1;
52
53
54 return start;
55
选择排序
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
时间复杂度：O(n^2)，最优时间复杂度：O(n^2),平均时间复杂度：O(n^2)
1public static void selectionSort1(Comparable[] a)
2 int length = a.length;
3 int min;
4 Comparable temp;
5 for (int i = 0; i < length; i++)
6 min = i;
7 for (int j = i + 1; j < length; j++)
8 if (a[j].compareTo(a[min]) < 0)
9 min = j;
10
11
12 temp = a[min];
13 a[min] = a[i];
14 a[i] = temp;
15
16
希尔排序
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
时间复杂度：根据步长而不同，最优时间复杂度：O(n),平均时间复杂度：根据步长而不同
1public static void shellSort(Comparable[] a)
2 int length = a.length;
3 int h = 1;
4 Comparable temp;
5 while (h < length / 3)
6 h = 3 * h + 1;
7
8 while (h >= 1)
9 for (int i = h; i < length; i++)
10 for (int j = i; j >= h && a[j].compareTo(a[j - h]) < 0; j -= h)
11 temp = a[j];
12 a[j] = a[j - h];
13 a[j - h] = temp;
14
15
16 h /= 3;
17
18
堆排序
- 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
时间复杂度：O(nlogn)，最优时间复杂度：O(nlogn),平均时间复杂度：O(nlogn)
1public static void heapSort(Comparable[] a)
2 int length = a.length;
3 Comparable temp;
查看详情
数据结构与算法小结——排序
...算法可以后面再接着补。 首先说排序，我把排序分成七大算法，分法如图： 1.插 查看详情
七大排序算法(代码片段)
目录一排序的概念二常见的排序算法(1)插入排序（2）选择排序（3）交换排序（4）归并排序三插入排序（1）直接插入排序1.直接插入排序的思想2.直接插入排序的思想图解3.直接插入排序的代码及运... 查看详情
总结一下一些经典排序算法~（纯纯大白话算法思想无代码）
文章目录冒泡排序选择排序插入排序希尔排序归并排序快速排序堆排序冒泡排序比较相邻的元素，如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的步骤，从开始第一对到结尾的最后一对。这一步... 查看详情
七大排序算法
各种排序的实现思路-冒泡排序（BubbleSort） -是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是... 查看详情
十大经典排序算法(代码片段)
前言说明十大排序算法可以说是每个程序员都必须得掌握的了，花了一天的时间把代码实现且整理了一下，为了方便大家学习，我把它整理成一篇文章，每种算法会有简单的算法思想描述，为了方便大家理解，我还找来了动图演... 查看详情
算法3七大排序之：直接插入排序和希尔排序
上一篇总结了直接选择排序和堆排序，这一篇要总结的是插入排序中的直接插入排序和希尔排序，我们主要从以下几点进行总结。1、直接插入排序及算法实现2、希尔排序及算法实现3、直接插入排序PK希尔排序 1、直接插入排... 查看详情
数据结构中的七大排序算法—2
今天为大家带来的是数据结构中的七大排序算法的其中两种：希尔排序和堆排序。本次的代码实现还是使用的C语言，编译器还是vs2013版本，希望接下来的内容可以帮助大家理解这两种排序。希尔排序 &n... 查看详情
java实现七大排序算法(代码片段)
文章目录基本概念1.排序2.稳定性一、直接插入排序1.原理2.排序过程3.代码实现4.性能分析二、希尔排序1.原理2.直接插入排序过程3.关于gap的取值4.代码实现5.性能分析三、选择排序1.原理2.排序过程3.代码实现4.性能分析四、堆排序... 查看详情
冒泡排序(代码片段)
冒泡排序是一个非常经典的排序方法，虽然其排序效率不是非常高，但是还是非常有必要了解一下其原理。我认为了解一个算法之前，或是用java实现其之前，还是通过图示的方式来了解比较好，一张图印在脑海，写啥都不是事... 查看详情
✨✨[数据结构]——最经典的七大排序（超详细近两万字教程，你值得拥有）✨✨(代码片段)
文章目录一，插入排序1，直接插入排序（1）基本思想（2）主要步骤（3）代码实现（4）性能分析2，希尔排序(1)基本思想(2)主要步骤(3)代码实现(4)性能分析二，选择排序1，直接选... 查看详情
经典排序算法-归并排序mergesort
经典排序算法-归并排序Mergesort原理,把原始数组分成若干子数组,对每个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到所有合并完,形成有序的数组举例无序数组[624159]先看一下每一个步骤下的状态,完了再看合... 查看详情
十大经典排序算法小结
排序可以说是套路最多的基本算法了，今天来了兴致，那就总结一下这十大排序算法吧。冒泡法：这可以算是知名度最高的算法之一了吧，可以说不会这个算法都不好意思说自己写过代码。冒泡排序是最简单的排序之一了，其大... 查看详情
java排序（七大排序合集）(代码片段)
七大排序1、冒泡排序1.1、排序过程图1.2、排序思想1.3、排序代码1.4、代码改进2、选择排序2.1、排序过程图2.2、排序思想2.3、排序代码2.4、代码改进——双向选择排序2.4.1、改进排序思想2.4.2、改进排序代码3、插入排序3.1、排序... 查看详情
常见14种经典排序算法（java代码实现）
想了解更多算法题可以关注微信公众号“数据结构和算法”，每天一题为你精彩解答。一，冒泡排序排序算法其实有很多，冒泡排序基本上算是最简单的一种排序算法了。他的原理就和他的名字一样，通过不断的比较把小的数据... 查看详情
一文搞掂十大经典排序算法(代码片段)
一文搞掂十大经典排序算法今天整理一下十大经典排序算法。1、冒泡排序——越小的元素会经由交换慢慢“浮”到数列的顶端算法演示算法步骤比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻... 查看详情
七大常见排序，你究竟懂几个？（上）(代码片段)
...选择和堆排序的实现及分析 首先我们先来看一下基本的七大排序，今天我们先一起学习前四个： 1、排序的概率及意义 排序：所谓排序，就是使一串记 查看详情
七大排序算法（插排，希尔，选择排序，堆排，冒泡，快排，归并）--图文详解(代码片段)
目录引言一、直接插入排序概念图文解析1、起始状态 2、循环时3、最后细节代码实现代码复杂度稳定性二、希尔排序概念图文解析1、算法实现2、设置增量 3、进行交换4、缩小增量代码实现代码时间复杂度空间复杂度稳定性三... 查看详情