1、选择排序。
时间复杂度。O(n^2)。
基本思想：从左到又，找出一个最小的数，然后和左边的起始位置交换，如此循环。
比如： 5 4 3 2 1 => 1 4 3 2 5 => 1 2 3 4 5
选择排序：不管待排序的数列，怎样，找出最小的数比较的次数都是一样的，时间比较稳定，有点小不稳定的就是，如果后面的数本来就有序，就不用交换位置了。总体而言：比较稳定。
public class SelectionSort {
// 我们的算法类不允许产生任何实例
private SelectionSort(){}
public static void sort(int[] arr){
int n = arr.length;
for( int i = 0 ; i < n ; i ++ ){
// 寻找[i, n)区间里的最小值的索引
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
if( arr[j] < arr[minIndex] )
minIndex = j;
swap( arr , i , minIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int[] arr = {10,9,8,7,6,5,4,3,2,1};
SelectionSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
System.out.println();
}
}
2、插入排序
时间复杂度。O(n^2)。
基本思想：从左到右，找出第一个排序错的数，插入到这个数应该在的位置，如此循环。
比如：5 4 3 2 1 =》 4 5 3 2 1 = 》 3 4 5 2 1 =》 2 3 4 5 1 =》 1 2 3 4 5
步骤1：从第二个位置4开始，4和5比较，4比5小，所以，5往后挪动1位，4插入5之前的位置。
步骤2：现在前面两位已经有序了。找第三位3，3比5小，5往后挪动一位，3比4小，4往后挪动一位，之后3插入4之前的位置。这样前面3位都有序了。
步骤3：以此内推。
插入排序：虽然时间复杂度是O(n2)。但是，如果待排序的数列，本来就比较有序，那么第二次循环的比较可以提前中断，大大减少了比较次数和挪动次数。所以，插入排序，对于比较有序的数列，比较适合。插入排序时间不稳定，最差是O(n2)。最好可以达到O(n)，比如已经有序的队列，扫描一遍就可以了。
public class InsertionSort{
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// 把要插入的数保存起来
Comparable e = arr[i];
// 要插入的数和它前面的数进行比较，前面的数大于它，则前面的数往后移动一位，空出一个位置供待插入的数插入
int j = i;
for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
}
}
3.冒泡排序
时间复杂度O(n^2)。
基本思想：跟气泡从底下往上升起一样。从左到右，从第一个元素开始，和后面的元素比较，如果前面的元素比后面你的元素大，则交换位置，大元素往上冒一级，依次类推。每次循环一边，都能找到最大的一个元素放到末尾。
比如：5 4 3 2 1 =》 4 5 3 2 1 =》 4 3 5 2 1 =》 4 3 2 5 1 =》 4 3 2 1 5
前面已经找到最大的元素5，放到了末尾。
再来：4 3 2 1 5 =》 3 4 2 1 5 =》 3 2 4 1 5 =》 3 2 1 4 5
又找到最大的元素4，放到末尾。依此循环。
冒泡算法：冒泡算法，如果如上一样进行，会产生大量的数据交换和比较。可以进行优化，每次循环，不进行交换，只找最大的数，找到后直接和末尾的元素进行交换，也就是每次循环，只交换一次数据。
优化后冒泡排序其实和选择排序差不多：选择排序，每次找最小的数，交换一次，排好位置。冒泡排序每次找最大的数，交换一次，排好位置。
/*
* 冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr={6,3,8,2,9,1};
//外层循环控制排序趟数。有多少个元素，就要找多少个最大值。
for(int i=0;i<arr.length-1;i++){
//内层循环控制每一趟排序多少次。上层循环一次，就找到了一个最大值，内存不需要再和已找到的最大值进行比较
for(int j=0;j<arr.length-1-i;j++){
// 前面的比后面的大，则交换位置
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
System.out.println();
System.out.println("排序后的数组为：");
for(int num:arr){
System.out.print(num+" ");
}
}
}
4、希尔排序
希尔排序是插入排序的高级优化版，相对比较复杂，也就缩小增量排序。
希尔排序的基本思想：选一个步长，比如n/2，n为数列的长度。然后按这个步长把数列分组。比如 5 4 3 2 1，步长n/2为2，所以，5 3 1为一组，4，2为一组。
然后每组用插入排序算法排序。第一组变成了1 3 5，第二组变成了2，4。原数组变成了12345。再缩小步长，缩小为一半:2/2=1，1 2 3 4 5为一组，再进行插入排序，变成了 1 2 3 4 5。
希尔排序：希尔排序让数列逐渐整体有序：固定步长的数是有序的，之后再缩小步长，又在前个步长有序的基础上，插入排序更简单。希尔排序会比插入排序快很多。
public void shellSort(int[] list) {
int gap = list.length / 2;
// 循环一次，则gap步长的每一组数列已经排好序。步长缩小一半
while (1 <= gap) {
// 从第gap开始，一个一个往后，找gap长的同组数据。
// 注意：这里并不是先排好一组后，再排另一组，而是按照坐标位置，组与组同时进行插入排序
for (int i = gap; i < list.length; i++) {
int j = 0;
int temp = list[i];
// 找到坐标为i的数据在同组数据中应该插入的位置，插入
for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
gap = gap / 2; // 减小增量
}
}
参考：理解希尔排序的排序过程
5、归并排序
时间复杂度：O(nlogn)。
基本思想：如果两个有序的数列，合并成一个有序的数列。把数列，拆分成两部分，再把每部分再拆分成两部分，如此循环，直到每部分不可再拆分，只剩一个元素，则每部分再有序合起来，合起来是有序的，再把合起来的有序数列和另外合起来的有序数列再合起来，如此，最后的数列就是有序的。
比如： 5 4 3 2 1 =》 543-21 =》54-3-2-1=》5-4-3-21，再合起来：45-3-21=》345-12=》12345
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r) {
if (l >= r)
return;
int mid = (l+r)/2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
private static void merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
System.out.println("l :" + l);
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
// 因为aux数组只是复制了arr的l到r+1的部分，所以，有l的偏移量
else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
归并算法的优化：
一、在两组数列合并的时候，如果第一组数列的最大的的元素小于第二组数列头部的元素，则第二组所有元素都比第一组大，所以不需要合并，本来就是有序的。
二、在数列长度比较小的时候，可以用插入排序排序。
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r) {
// 优化2: 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
InsertionSort.sort(arr, l, r);
return;
}
int mid = (l+r)/2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
// 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if( arr[mid].compareTo(arr[mid+1]) > 0 )
merge(arr, l, mid, r);
}
private static void merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
从左到右不递归拆分数列：归并排序的拆分数列方面，不使用递归拆分，从左到右拆分也可以，比如：54321=54一组，32一组，1一组
public static void sort(Comparable[] arr){
int n = arr.length;
// Merge Sort Bottom Up 无优化版本
// for (int sz = 1; sz < n; sz *= 2)
// for (int i = 0; i < n - sz; i += sz+sz)
// // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
// merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));
// 对于小数组, 使用插入排序优化
for( int i = 0 ; i < n ; i += 16 )
InsertionSort.sort(arr, i, Math.min(i+15, n-1) );
for( int sz = 16; sz < n ; sz += sz )
for( int i = 0 ; i < n - sz ; i += sz+sz )
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
if( arr[i+sz-1].compareTo(arr[i+sz]) > 0 )
merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1) );
}
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
6、快速排序
时间复杂度：nlog(n)。
基本思想：选择数列中的一个数，然后遍历数列，大于这个数的放右边，小于这个数的放左边，之后再针对左边和右边又进行如此操作，最后达到一个有序的集合。
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r){
if( l >= r )
return;
// 左右分区
int p = partition(arr, l, r);
// 左边分区递归
sort(arr, l, p-1 );
// 右边分区递归
sort(arr, p+1, r);
}
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
private static int partition(Comparable[] arr, int l, int r){
Comparable v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for(int i = l + 1 ; i <= r ; i ++ )
// 左边的大于标准量，则左边和右边换位置
if( arr[i].compareTo(v) < 0 ){
j ++;
swap(arr, j, i);
}
// 把标准量放到中间，左边是大于标准量，右边是小于标准量
swap(arr, l, j);
return j;
}
快速排序优化：1、如果对一个比较有序的数组，标准量总是取第一个的话，第一个可能总是最小的，那么以这个标准量分区的时候，左右两边严重不均匀，结果快速排序就好像成了选择排序，每次只是找到了最小的。产生了大量递归，大量比较。所以，可以用随机坐标为标准量。2、对于数列长度小的，可以用插入排序。
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
private static int partition(Comparable[] arr, int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
Comparable v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i].compareTo(v) < 0 ){
j ++;
swap(arr, j, i);
}
swap(arr, l, j);
return j;
}
// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r){
// 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
InsertionSort.sort(arr, l, r);
return;
}
int p = partition(arr, l, r);
sort(arr, l, p-1 );
sort(arr, p+1, r);
}
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
双路快速排序：针对上面的快速排序，如果待排序的数列，有大量重复的元素，那么，根据上面排序的分区方法，和标准量相等的元素都在右边分区，造成分区的不均匀。优化方法就是：把相等的元素分布到分区两边。
双路快速排序的思想：从左扫描，扫描到和标准量相等或者大于的数停止，再从右扫描，扫描到和标准量相等或小于的数停止，从左和从右也就是双路的意思。扫描完之后，中间的部分可能就有和标准量相等的元素，再把从左扫描的停止位（这个位置的数可能是等于标准量，可能是大于标准量）,和从右扫描的停止位（这个位置的数可能是等于标准量，可能是小于标准量），交换位置，之后，左右停止位加1，再继续扫描，直到，左右停止位相碰为止。这样，相等的元素就会被分配到两边了。
private static int partition(Comparable[] arr, int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
Comparable v = arr[l];
// arr[l+1...i) <= v; arr(j...r] >= v
int i = l+1, j = r;
while( true ){
// 注意这里的边界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0
// 思考一下为什么?
while( i <= r && arr[i].compareTo(v) < 0 )
i ++;
// 注意这里的边界, arr[j].compareTo(v) > 0, 不能是arr[j].compareTo(v) >= 0
// 思考一下为什么?
while( j >= l+1 && arr[j].compareTo(v) > 0 )
j --;
// 对于上面的两个边界的设定, 有的同学在课程的问答区有很好的回答:)
// 大家可以参考: http://coding.imooc.com/learn/questiondetail/4920.html
if( i > j )
break;
swap( arr, i, j );
i ++;
j --;
}
swap(arr, l, j);
return j;
}
三路快速排序：二路快速排序，相等的元素并不一定会均匀的分布在两个区，而且，分配到两个区的相等的元素还要和普通元素一样再进行分区处理。所以：三路排序的优化方向是：分三个区，小于、等于、大于。对于等于区不需要进行处理。
三路排序的思路：左指针lt，又指针gt，遍历的指针i，i对应的元素小于标准量，则和左指针对应的元素的后一个元素交换位置，并且i++，左指针往右移动一格，如果i对应的元素大于标准量，则i和右指针对应的元素的左边一个元素交换，右指针往左移动一格，i指针不需要加1，因为刚才从右指针左边一个元素交换过来的数还没有进行比较判定，如果i对应的元素等于标准量，则i++，左右指针不移动。如此，就分好了三个区，之后只要对左右分区再递归处理，不需要对中间分区处理。
private static void sort(Comparable[] arr, int l, int r){
// 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
InsertionSort.sort(arr, l, r);
return;
}
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr, l, (int)(Math.random()*(r-l+1)) + l );
Comparable v = arr[l];
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l+1; // arr[lt+1...i) == v
while( i < gt ){
if( arr[i].compareTo(v) < 0 ){
swap( arr, i, lt+1);
i ++;
lt ++;
}
else if( arr[i].compareTo(v) > 0 ){
swap( arr, i, gt-1);
gt --;
}
else{ // arr[i] == v
i ++;
}
}
swap( arr, l, lt );
sort(arr, l, lt-1);
sort(arr, gt, r);
}
题外话：比较算法中，快速排序和归并排序时间复杂度olg(n）,是比较排序算法中比较好的算法。jdk6的arrays.sort采用的是归并排序，jdk7的Arrays.sort的排序算法是timsort（归并排序的优化版）。
网友评论