Java排序算法
智博程序园 人气:0前言
本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备，以及个人的心得体会，汇集成本篇文章，作为自己对排序算法理解的总结与笔记。
内容主要是关于十大经典排序算法的简介、原理、动静态图解和源码实现的分析。
对于一名程序员来讲，我们都知道数据结构与算法起初是用于C语言居多，然而在Java语言下使用算法的案例却很少，因此，特别整理了在Java开发环境的排序算法，供大家一起学习探讨。
一、排序算法
1.排序算法概述（百度百科）
所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。
2.《数据结构与算法》中的排序算法
常见的排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
算法图解（菜鸟教程借图）：
图解分析：
3.算法分析
时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
- n：数据规模
- k："桶"的个数
- In-place：占用常数内存，不占用额外内存
- Out-place：占用额外内存
- 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
平均时间复杂度是指所有可能的输入实例均以等概率的出现情况下得到算法的运行时间
最坏时间复杂度，一般讨论的时间复杂度均是最坏情况下的时间复杂度，这样做的原因是最坏情况下的时间复杂度是算法在任何输入实例上运行的界限，这就保证了算法的运行时间不会比最坏情况更长。
平均时间复杂度和最坏时间复杂度是否一样，这就需要根据算法不同而不同了。
二、十大经典排序算法（Java开发版）
PS：案例均以数组{15，63，97，12，235，66}排序为例
1.冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
1.1实现原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1.2动图演示
1.3实例展示
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arrays =new int[]{15,63,97,12,235,66};
for (int i=0;i<arrays.length-1;i++){
// 控制比较次数,三者交换，实现排序
for(int j=0;j<arrays.length-1-i;j++){
if (arrays[j] > arrays[j+1]){
int temp = 0;//类似空桶
temp = arrays[j]; //A桶中水倒入空桶C中
arrays[j] = arrays[j+1];//把B桶的水倒入A桶中
arrays[j+1] = temp;//把C桶的水倒入B桶中
}
}
}
System.out.println(Arrays.toString(arrays));
}
}排序结果展示：
2.快速排序
快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进。
2.1实现原理
快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2.2 动图演示
2.3实例展示
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arrays = new int[]{15,63,97,12,235,66};
sort(arrays,0,arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
public static void sort(int[] arrays,int left,int right){
int l = left;
int r = right;
int pivot = arrays[(left+right)/2];
int temp = 0;
while (l<r){
//在左边查找小于中间值的
while(arrays[l]<pivot){
l++;
}
//查询右边小于中间值
while (arrays[r]>pivot){
r--;
}
if (l>=r){
break;
}
temp = arrays[l];
arrays[l] = arrays[r];
arrays[r] = temp;
// 交换完数据arrays[l] = pivot
if (arrays[l]==pivot){
r--;
}
if (arrays[r]==pivot){
l++;
}
if (r==l){
l++;
r--;
}
if (left<r){
sort(arrays,left,r);
}
if (right>l){
sort(arrays,l,right);
}
}
}
}排序结果展示：
3.基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序是1887年赫尔曼、何乐礼发明的。思想是讲整数按位数切割成不同的数字，然后按每个位数分别比较。
3.1实现原理
讲所有的待比较数值统一设置为同样的数位长度，位数比较短的数前面补零，然后从最地位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
3.2 动图演示
3.3实例展示
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class BasicSort {
public static void main(String[] args) {
int[] arrays = new int[]{15,63,97,12,235,66};
SimpleDateFormat simpleDateFormat =new SimpleDateFormat("yyyy-mm-dd HH:MM:ss:SS");
System.out.println("开始排序前:"+simpleDateFormat.format(new Date()));
sort(arrays);
System.out.println("排序结束:"+simpleDateFormat.format(new Date()));
}
// 1.获取原序列的最大位多少
// @param arrays
public static void sort(int[] arrays){
// 获取最大位数
int max = 0;
for(int i=0;i<arrays.length;i++){
if (arrays[i]>max){
max = arrays[i];
}
}
// 获取字符串长度，所以把int类型转字符串类型
int maxLength = (max+"").length();
// 定义二维数组，大小10，表示10个桶，每一个桶则是一个数组
// [[],[],[],[],[]...]
int[][] bucket = new int[10][arrays.length];
// 辅助数组
int[] bucketElementCount = new int[10];
// 循环获取无序数列
for (int j=0;j<arrays.length;j++){
int locationElement = arrays[j]%10;
// 放入桶中
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j] ;
bucketElementCount[locationElement]++;
}
// 遍历每一个桶，讲元素存放原数组中
int index = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l = 0;l<bucketElementCount[k];l++){
arrays[index++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
System.out.println(Arrays.toString(arrays));
// 第一轮针对个位数进行比较
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/1%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出来按照桶的顺序放回原数组中
int indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
// 判断十位数
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/10%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出来按照桶的顺序放回原数组中
indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
// 获取百位数比较
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/100%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出来按照桶的顺序放回原数组中
indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
System.out.println("基数排序后的顺序:"+Arrays.toString(arrays));
}
}排序结果展示：
4.插入排序
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
4.1实现原理
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
4.2 动图演示
4.3实例展示
public class InsertSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
//控制拿去每一个元素
for(int i=1;i<array.length;i++){
//比较次数
for (int j=i;j>=1;j--){
//是否小于前面的元素
if (array[j]<array[j-1]){
int temp = 0;
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}else {
//continue 与 break
break;
}
}
}
System.out.println("排序后的结果："+ Arrays.toString(array));
}
}排序结果展示：
5.选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
5.1实现原理
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
5.2 动图演示
5.3实例展示
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[]{15,63,97,12,235,66};
for (int i=0;i<arr.length;i++){
for (int j=arr.length-1;j>i;j--){
if (arr[j]<arr[i]){
int temp = 0;
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
System.out.println("选择排序后的结果:"+ Arrays.toString(arr));
}
}排序结果展示：
6.希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
6.1实现原理
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2
般的初次取序列的一半为增量，以后每次减半，直到增量为1。
6.2 动图演示
6.3实例展示
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
// 实现增量变化
for (int gap = array.length/2;gap>0;gap/=2){
for (int i=gap;i<array.length;i++){
for (int j=i-gap;j>=0;j-=gap){
if (array[j]>array[j+gap]){
int temp = 0;
temp = array[j];
array[j] = array[j+gap];
array[j+gap] = temp;
}
}
}
}
System.out.println(Arrays.toString(array));
}
}排序结果展示：
7.归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
7.1实现原理
- 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾
我们需要将两个已经有序的子序列合并成一个有序序列，比如上图最后一次合并，将[2,4,5,6]和[1,3,7,8]已经有序的子序列合并最终序列[1,2,3,4,5,6,7,8]
7.2 动图演示
7.3实例展示
import java.util.Arrays;
public class MSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
//临时数组
int[] temp = new int[array.length];
sort(array,0,array.length-1,temp);
System.out.println(Arrays.toString(array));
}
public static void sort(int[] array,int left,int right,int[] temp){
if (left<right){
// 求出中间值
int mid = (left+right)/2;
// 向左边分解
sort(array,left,mid,temp);
// 向右边分解
sort(array,mid+1,right,temp);
// 合并数据
sum(array,left,right,mid,temp);
}
}
/**
* 合并元素
* @param array
* @param left
* @param right
* @param mid
* @param temp
*/
public static void sum(int[] array,int left,int right,int mid,int[] temp){
int i = left;
int j = mid+1;
// 指向临时数组下标
int t = 0;
// 开始循环比较左右两遍数组元素比较
while (i<=mid && j<=right){
if (array[i]<=array[j]){
temp[t] = array[i];
t++;
i++;
}else {
temp[t] = array[j];
t++;
j++;
}
}
// 把剩余的元素直接存放在临时数组中
while(i<=mid){
temp[t] = array[i];
t++;
i++;
}
while (j<=right){
temp[t] = array[j];
t++;
j++;
}
// 临时数组中的元素拷贝至原数组中
int tempIndex = left;
int k = 0;
while (tempIndex<=right){
array[tempIndex] = temp[k];
k++;
tempIndex++;
}
}
75 }排序结果展示：
8.计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）
8.1实现原理
假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：
- 扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；
- 扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。
8.2 动图演示
8.3实例展示
public class CountSort {
public static void main(String[]args){
//排序的数组
int a[]={15,63,97,12,235,66};
int b[]=countSort(a);
for(int i:b){
System.out.print( i+",");
}
System.out.println();
}
public static int[] countSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//这里k的大小是要排序的数组中，元素大小的极值差+1
int k=max-min+1;
int c[]=new int[k];
for(int i=0;i<a.length;++i){
c[a[i]-min]+=1;//优化过的地方，减小了数组c的大小
}
for(int i=1;i<c.length;++i){
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}
}排序结果展示：
9.堆排序
堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
9.1实现原理
- 创建一个堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互换；
- 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
- 重复步骤 2，直到堆的尺寸为 1。
9.2 动图演示
9.3实例展示
public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}排序结果展示：
10.桶排序
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
10.1实现原理
假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
10.2 动图演示
然后，元素在每个桶中排序：
10.3实例展示
public static void basket(int data[])//data为待排序数组
{
int n=data.length;
int bask[][]=new int[10][n];
int index[]=new int[10];
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++)
{
max=max>(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());
}
String str;
for(int i=max-1;i>=0;i--)
{
for(int j=0;j<n;j++)
{
str="";
if(Integer.toString(data[j]).length()<max)
{
for(int k=0;k<max-Integer.toString(data[j]).length();k++)
str+="0";
}
str+=Integer.toString(data[j]);
bask[str.charAt(i)-'0'][index[str.charAt(i)-'0']++]=data[j];
}
int pos=0;
for(int j=0;j<10;j++)
{
for(int k=0;k<index[j];k++)
{
data[pos++]=bask[j][k];
}
}
for(intx=0;x<10;x++)index[x]=0;
}
}排序结果展示：
加载全部内容