java快速排序算法图解,Java常见排序算法
00-1010前言1。排序算法1。排序算法概述(百度百科)2。《数据结构与算法》中的排序算法3。算法分析2。十大经典排序算法(Java开发版)1。冒泡排序2。快速排序3。基数排序4。插入排序5。选择排序6。希尔排序7。合并排序8。计数排序9。堆排序10。
00-1010本文主要是阐述我在学习Java开发环境排序算法时的个人准备，以及我的个人体会。本文是我对排序算法理解的总结和笔记。
内容主要是十大经典排序算法的介绍、原理、动静态图以及源代码实现分析。
对于一个程序员来说，我们都知道数据结构和算法最开始大多用在C语言中，而在Java语言中使用算法的情况很少。所以特意把Java开发环境中的排序算法整理出来，供大家一起学习讨论。
目录
00-1010所谓排序算法，是指通过特定的算法因子，按照既定的模式对一组或多组数据进行重新排序。这个新的序列遵循一定的规则，也反映了一定的规则。因此，处理后的数据易于筛选和计算，大大提高了计算效率。对于排序，我们首先要求它具有一定的稳定性，即当两个相同的元素同时出现在某个序列中时，经过一定的排序算法，它们排序前后的相对位置不会发生变化。换句话说，即使两个相同的元素在排序过程中不同，也不允许混淆。
00-1010常见的排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
算法图(借用菜鸟教程):
图形分析：
前言
时间复杂度
平方顺序(O(n2))排序各种简单排序：直接插入，直接选择和冒泡排序。
线性对数序(O(nlog2n))排序快速排序、堆排序和归并排序；
O (n1))和(是介于0和1之间的常数。谢尔分类
线性顺序(O(n))排序基数排序，此外还有桶和箱排序。
关于稳定性
稳定排序算法：冒泡排序、插入排序、合并排序和基数排序。
不是一个稳定的排序算法：选择排序，快速排序，希尔排序和堆排序。
名词解释：
n:数据大小K:就地桶数：占用常量内存，不占用额外内存Out-place:占用额外内存稳定性：排序后两个相等键值的顺序与排序前相同。平均时间复杂度是指当所有可能的输入实例以相等的概率出现时算法的运行时间。
最坏时间复杂度,通常讨论的时间复杂度是最坏情况下的时间复杂度。这样做的原因是最坏情况时间复杂度是算法在任何输入实例上运行的极限，这保证了算法的运行时间不会长于最坏情况。
无论平均时间复杂度和最坏时间复杂度是否相同，这需要根据不同的算法而有所不同。
00-1010PS:以数组{15，63，97，12，235，66}为例，对所有案例进行排序。
00-1010冒泡排序是计算机科学领域中一种简单的排序算法。
它重复访问要排序的元素列表，依次比较两个相邻的元素，如果顺序(例如从大到小，从Z到A的首字母)错误，则交换它们。重复访问元素的工作，直到没有相邻的元素需要交换，也就是说，元素列已经排序。
这种算法的名字来源于较小的元素会通过交换慢慢“浮”到数列的顶端(按升序或降序)，就像碳酸饮料中二氧化碳的气泡最终会浮到顶端一样，因此得名“气泡排序”。
1.1实现原理
比较相邻的元素。如果第一个比第二个大，两个都换。对每一对相邻的元素做同样的工作，从开始的第一对到结束的最后一对。此时，最后一个元素应该是最大的数字。对除最后一个元素之外的所有元素重复上述步骤。每次对越来越少的元素重复上述步骤，直到没有要比较的数字对。
1.2动图演示
1.3实例展示
class="brush:java;"> 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; } }排序结果展示：
以上就是Java十大经典排序算法的实现图解的详细内容，更多关于Java排序算法的资料请关注盛行IT其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。