十大经典排序算法总结（含Java代码实现）

最近几天在研究排序算法，看了许多博客，发明网上有的文章中对排序算法表明的并不是很透彻，并且有许多代码都是错误的，譬喻有的文章中在“桶排序”算法中对每个桶举办排序直接行使了Collection.sort()函数，这样固然能到达结果，但对付算法研究来讲是不行以的。

以是我按照这几天看的文章，清算了一个较为完备的排序算法总结，本文中的全部算法均有JAVA实现，经本人调试无误后才发出，若有错误，请列位先进指出。

0、排序算法声名

0.1 排序的界说

对一序列工具按照某个要害字举办排序。

0.2 术语声名

• 不变：假如a本来在b前面，而a=b，排序之后a如故在b的前面;
• 不不变：假如a本来在b的前面，而a=b，排序之后a也许会呈此刻b的后头;
• 内排序：全部排序操纵都在内存中完成;
• 外排序：因为数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才气举办;
• 时刻伟大度：一个算法执行所淹灭的时刻。
• 空间伟大度：运行完一个措施所需内存的巨细。

参考：不变排序与不不变排序

0.3 算法总结

图片名词表明：

• n: 数据局限
• k: “桶”的个数
• In-place: 占用常数内存，不占用特殊内存
• Out-place: 占用特殊内存

0.4 算法分类

0.5 较量和非较量的区别

常见的快速排序、合并排序、堆排序、冒泡排序等属于较量排序。在排序的最终功效里，元素之间的序次依靠于它们之间的较量。每个数都必需和其他数举办较量，才气确定本身的位置。

在冒泡排序之类的排序中，题目局限为n，又由于必要较量n次，以是均匀时刻伟大度为O(n²)。在合并排序、快速排序之类的排序中，题目局限通过度治法消减为logN次，以是时刻伟大度均匀O(nlogn)。

较量排序的上风是，合用于各类局限的数据，也不在乎数据的漫衍，都能举办排序。可以说，较量排序合用于统统必要排序的环境。

计数排序、基数排序、桶排序则属于非较量排序。非较量排序是通过确定每个元素之前，应该有几多个元向来排序。针对数组arr，计较arr[i]之前有几多个元素，则独一确定了arr[i]在排序后数组中的位置。

非较量排序只要确定每个元素之前的已有的元素个数即可，全部一次遍历即可办理。算法时刻伟大度O(n)。

非较量排序时刻伟大度底，但因为非较量排序必要占用空间来确定独一位置。以是对数据局限和数据漫衍有必然的要求。

1、冒泡排序(Bubble Sort)

冒泡排序是一种简朴的排序算法。它一再地走访过要排序的数列，一次较量两个元素，假如它们的次序错误就把它们互换过来。走访数列的事变是一再地举办直到没有再必要互换，也就是说该数列已经排序完成。

这个算法的名字由来是由于越小的元素会经过互换逐步“浮”到数列的顶端。冒泡排序先容：冒泡排序

1.1 算法描写

较量相邻的元素。假如第一个比第二个大，就互换它们两个;

对每一对相邻元素作同样的事变，从开始第一对到末了的最后一对，这样在最后的元素应该会是最大的数;

针对全部的元素一再以上的步调，除了最后一个;

一再步调1~3，直到排序完成。

1.2 动图演示

1.3 代码实现

/** 
 * 冒泡排序 
 * 
 * @param array 
 * @return 
 */ 
 public static int[] bubbleSort(int[] array) { 
 if (array.length == 0) 
 return array; 
 for (int i = 0; i < array.length; i++) 
 for (int j = 0; j < array.length - 1 - i; j++) 
 if (array[j + 1] < array[j]) { 
 int temp = array[j + 1]; 
 array[j + 1] = array[j]; 
 array[j] = temp; 
 } 
 return array; 
 } 

1.4 算法说明

最佳环境：T(n) = O(n) 最差环境：T(n) = O(n2) 均匀环境：T(n) = O(n2)

2、选择排序(Selection Sort)

示意最不变的排序算法之一，由于无论什么数据进去都是O(n2)的时刻伟大度，以是用到它的时辰，数据局限越小越好。独一的甜头也许就是不占用特另外内存空间了吧。理论上讲，选择排序也许也是平常排序一样平常人想到的最多的排序要领了吧。

选择排序(Selection-sort)是一种简朴直观的排序算法。它的事变道理：起首在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继承探求最小(大)元素，然后放到已排序序列的末端。以此类推，直到全部元素均排序完毕。选择排序先容：选择排序

2.1 算法描写

n个记录的直接选择排序可颠末n-1趟直接选择排序获得有序功效。详细算法描写如下：

初始状态：无序区为R[1..n]，有序区为空;

第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区别离为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出要害字最小的记录 R[k]，将它与无序区的第1个记录R互换，使R[1..i]和R[i+1..n)别离变为记录个数增进1个的新有序区和记录个数镌汰1个的新无序区;

n-1趟竣事，数组有序化了。

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!