排序算法可分为8种，如图所示。外部排序只有在数据非常大时(超过10亿)。
一. 冒泡排序(每次一次，比较两两次，后面放大或小的数字(交换位置)
package com.bzw.sort; import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] array = {5,4,3,2,1}; boolean flag = false; int count = 0; for (int i=0;i array[j 1]){ flag = true; int temp = array[j]; array[j] = array[j 1]; array[j 1] = temp; } count ; } if (!flag){ ///在一次遍历中没有交换一次，说明排名已经完成，不必回收 break; } else { flag = false; } } System.out.println(Arrays.toString(array)); System.out.println("遍历次数" count); } } 二. 简单选择排序(假设第一个数字是最大值或最小值，然后在遍历中找到真正的最小值，交换位置)
package com.bzw.sort; import java.util.Arrays; public class ChooseSort { public static void main(String[] args) { int[] array = {4,3,-2,6,5}; for (int i=0;i 三. 直接插入排序(从头开始，每次将一个数字与前面的数字进行比较，当一个数字与这个数字进行比较时，插入这个数字后面。
package com.bzw.sort; import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] array = {2, 1, 5, -3, 4, 2, -5, 9}; // 自己写的代码，没有老师写的通俗易懂 // for (int i=0;i= 0 && insertVal < array[insertIndex]) { array[insertIndex 1] = array[insertIndex]; insertIndex--; } //insertIndex 1 即要插入的位置 array[insertIndex 1] = insertVal; } System.out.println(Arrays.toString(array)); } } 四. 希尔排名(可以看作是直接插入排名的优化，直接插入排名的一个缺点是，当一个较小的数字在后面时，它应该经历更多次。希尔排名可以解决这个问题。它的想法是将数组分成几部分(array.length/2)然后用直接插入法对每份进行排序，直到最后只剩下一组。
package com.bzw.sort; import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] array = {-3,4,2,1,3}; shellSort(array); System.out.println(Arrays.toString(array)); } // 试着自己写，没写出来 // public static void shellSort(int[] array,int n){ // int[] temp1 = new int[array.length]; // int[] temp2 = new int[array.length]; // while (n != 1){ // for (int j=0;j= 0 && insertVal < array[insertIndex]){ // array[insertIndex n] = array[insertIndex]; // insertIndex = i - n; // } // // array[insertIndex n] = insertVal; // } // } public static void shellSort(int[] array){ for (int grap = array.length/2;grap > 0;grap /= 2){ //grap 步长，即分组的长度
for (int i = grap;i < array.length;i++){
// 因为后面代码要对i值进行修改，所以把当前的i值和数组值存到一个变量中
int temp = array[i];
int j = i;
if (temp < array[j - grap] ){
while (j - grap >= 0 && temp < array[j - grap]){
array[j] = array[j - grap];
j = j - grap; //每次减少一个步长，确保在同一个组内移动
}
array[j] = temp;
}
}
}
}
}
五. 快速排序(可以看成是冒泡排序的优化。它的思想是先选择一个数，然后将比这个数大的放在一边，比这个数小的放在一边，然后用递归实现排序。因为用的是递归，快排还是比较快的。)
package com.bzw.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class QuickSort {
public static void main(String[] args) {
// int[] array = {4,3,-1,78,45,0,3,10};
int[] array = new int[80000000];
for (int i=0;i pivot){
r --;
}
if (l >= r){
break;
}
temp = array[l];
array[l] = array[r];
array[r] = temp;
if (array[r] == pivot){ //交换完如果发现 array[r] == pivot，要将左下标手动向后移一位，
l ++; // 不然 l 就不会动了，造成死循环(可以举个相等的例子，画图理解)
}
if (array[l] == pivot){ //右下标同理
r --;
}
}
// 当 l == r 必须l++,r-- 否则出现栈溢出
// 当l == r时，如果不手动l++,r--的话，l和r的值将不在发生变化(因为没有其他代码使其变化),那么递归的条件将不会发生改变，
// 递归函数不停的压栈，最终导致栈溢出
if (l == r){
l ++;
r --;
}
if (left < r){
quickSort(array,left,r);
}
if (l < right){
quickSort(array,l,right);
}
}
}
六. 归并排序(采用分治策略，将一个数组分解成一个个的数，再进行合并，最终完成排序。合并的思路：将左面的一组和右面的一组进行比较，将较小的或较大的数放到一个临时数组中，最后将这个临时数组再复制原数组。)
package com.bzw.sort;
import java.util.Arrays;
public class MergerSort {
public static void main(String[] args) {
int[] array = {6,29,17,9,3,11,-3,0,4};
int[] temp = new int[array.length];
mergerSort(array,0,array.length-1,temp);
System.out.println(Arrays.toString(array));
}
//分解 + 合并
public static void mergerSort(int[] array,int left,int right,int[] temp){
if (left < right){
int mid = (left + right) / 2;
//向左递归分解
mergerSort(array,left,mid,temp);
//向右递归分解
mergerSort(array,mid+1,right,temp);
//合并
merger(array,left,right,mid,temp);
}
}
//合并
public static void merger(int[] array ,int left,int right,int mid,int[] temp ){
int l = left;
int j = mid + 1;
int t = 0;
while (l <= mid && j <= right){
if (array[l] <= array[j]){
temp[t] = array[l];
t++;
l++;
}else {
temp[t] = array[j];
t++;
j++;
}
}
while (l <= mid){
temp[t] = array[l];
t++;
l++;
}
while (j <= right){
temp[t] = array[j];
t++;
j++;
}
//把temp中的值复制到array中，这里的tempLeft表明复制到array哪个位置。
t = 0;
int tempLeft = left;
while (tempLeft <= right){
array[tempLeft] = temp[t];
tempLeft++;
t++;
}
}
}
七. 基数排序(桶排序的扩展，它的思想很简单，把一组数先按个位数字的大小排序，再按十位数字的大小排序，然后百位，千位.........。所以需要10个桶(一位数组)分别表示0-9 十个数，而且也不能确定每个桶中有多少的数，只能按最坏的情况算，即每个桶的大小都是和原数组大小一样。这样有时候就会造成空间的浪费，基数排序就是空间换时间的经典算法。)
package com.bzw.sort;
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] array = {3,35,3,0,9,7};
radixSort(array);
System.out.println(Arrays.toString(array));
}
public static void radixSort(int[] array){
//用一个二维数组表示桶和桶中的数据，比如bucket[1][2] = 31 表示编号为1的桶在第二个位置有个数是31
int[][] bucket = new int[10][array.length];
//表示桶中有多少个数，比如bucketElement[4] = 3 表示编号为4这个桶中有3个数据(有一个数组来存储，便于后面将值取出赋给array)
int[] bucketElement = new int[10];
int max = array[0];
for (int i = 0;i < array.length;i++){
if (array[i] > max){
max = array[i];
}
}
int length = (max + "").length();//最大值的位数
// System.out.println(length);
for (int j = 0,n = 1;j < length;j++,n = n * 10){
for (int i = 0;i < array.length;i++){
int data = array[i] / n % 10;
bucket[data][bucketElement[data]] = array[i];
bucketElement[data]++;
}
int index = 0;
for (int k = 0;k
八. 总结
稳定表示，如果两个相同的数，在排序过后，原来在前面的那个数仍然在前面。不稳定就不确定了。
In-place表示没有额外占用空间，Out-place表示有额外占用空间。
当数的规模较大的时候(超过2^10)，用基数排序较快。
