JAVA排序算法总结
1、排序方法的分类：
插入类排序：直接插入排序、希尔排序
交换类排序：冒泡排序、快速排序
选择类排序：简单选择排序、堆排序
归并类排序：归并排序。
2、总结
各种排序算法的性能对比如下
| 排序类型 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(nlogn) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) | 稳定 |
| 快速排序 | O(nlog₂n) | O(nlog₂n) | O(n²) | O(nlog₂n) | 不稳定 |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(1) | 不稳定 |
| 基数排序 | O(n*k) | O(n*K) | O(n*k) | O(n+k) | 稳定 |
从时间复杂度来说：
- 平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；
- 线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；
- O(n1+§))排序，§是介于0和1之间的常数：希尔排序
- 线性阶O(n)排序：基数排序，此外还有桶、箱排序。
3、冒泡排序
它是最简单也是最慢的排序方法，双层for循环对每两项数值进行比较交换
算法描述：依次比较相邻元素的值，若发现逆序则交换，使值较大的原色逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
/**
* 冒泡排序
* @param array
*/
public static void maoPao(int []array){
int temp;
for(int i=1;i<array.length;i++) {
for(int j=0;j<array.length-1-i;j++) {
if(array[j]>array[j+1]) {
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
} 4、选择排序
循环遍历整个数组，不断把最小的值放到前面
/**
* 选择排序
* @param array
*/
public static void xuanZe(int []array) {
int index,temp;
for(int i=0;i<array.length-1;i++) {
index=i;//用来记住数组元素的下标
for(int j=i+1;j<array.length;j++) {
if(array[index]>array[j]) {
index=j;//只对index值改变，不交换元素位置
}
}
if(i!=index) {
temp=array[index];
array[index]=array[i];
array[i]=temp;
}//一轮排序进行一次数组位置交换
System.out.print("第"+i+"次：");
}
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
} 5、插入排序
便利整个数组，不断插入较小的数字到已排号顺序的部分中
/**
* 插入排序
* @param array
*/
public static void chaRu(int []array) {
int temp;
for(int i=1;i<array.length;i++) {
int j=i;
temp = array[i];
while( j>0 && temp < array[j-1]) {
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
} 6、快速排序
采用分治的思想，先取中间值，分别从双端比较，把左端换成都比中间值小的，右端都比中间值大，然后重复此操作
/**
* 快速排序
* @param array
* @param left
* @param right
*/
public static void kuaiSu(int []array,int left,int right){
if(left < right) {
int i=left,j=right;
int pivot = array[left];//选择最左边的元素作为中间值
/**
* 分治
*/
while(i < j) {
while(i < j && array[j] >= pivot) {
j--;
}
if(i < j) {
array[i] = array[j];
i++;
}
while(i < j&& array[i] < pivot){
i++;
}
if(i < j) {
array [j] =array [i];
j--;
}
}
array [i]=pivot;
//递归
kuaiSu(array,left,i-1);
kuaiSu(array,i+1,right);
}
} 7、二分查找排序
与直接插入一样，只是找合适的插入位置的方式不同，这里是按照二分法找到合适的位置，可以减少比较的次数
/**
* 二分查找插入排序
* @param a
*/
public class ERFENCHAZHAO {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String[] nums = null;
System.out.println("请输入一组整数，以空格分隔：");
nums = scanner.nextLine().split(" ");
int[] array = new int[nums.length];
int sum = 0;
for (int i = 0; i < array.length; i++) {
array[i] = Integer.valueOf(nums[i]);
}
erFenChaZhao(array);
}
public static void erFenChaZhao(int[] a){
for (int i=0;i<a.length;i++){
int temp=a[i];
int left=0;
int right=i-1;
int mid=0;
while (left<=right){
mid=(left+right)/2;
if (temp<a[mid]){
right=mid-1;
}else {
left=mid+1;
}
}
for (int j=i-1;j>=left;j--){
a[j+1]=a[j];
}
if (left!=i){
a[left]=temp;
}
}
for(int i=0;i<a.length;i++) {
System.out.print(a[i] + " ");
}
}
}
8、希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
先取一个正整数d1 < n, 把所有相隔d1的记录放一组，每个组内进行直接插入排序；然后d2 < d1，重复上述分组和排序操作；直至di = 1，即所有记录放进一个组中排序为止。
/**
* 希尔排序
* @param array
*/
/**
* 希尔排序的原理:根据需求，如果你想要结果从小到大排列，它会首先将数组进行分
组，然后将较小值移到前面，较大值移到后面，最后将整个数组进行插入排序，
这样比起一开始就用插入排序减少了数据交换和移动的次数，
* 可以说希尔排序是加强 版的插入排序 拿数组5, 2,8, 9, 1, 3，4来说，数组长
度为7，当increment为3时，数组分为两个序列
* 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其
下标值小increment的数组值相比较
* 此例子是按照从小到大排列，所以小的会排在前面，第一次排序后数组为5, 1, 3,
4, 2, 8，9
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序， 实现数组从大到
小排
*/
public class shell {
public static void shellSort(int[] arr) {
// 空数组 或 只有一个元素的数组，则什么都不做。
if (arr == null || arr.length <= 1) return;
// 定义希尔增量。
int gap = arr.length / 2;
// gap缩小到0的时候就退出循环。
while (gap != 0) {
// 每组进行直接插入排序。
for (int i = gap; i < arr.length; i++) { // i 代表待插入元素的索引。
int value = arr[i];
int j = i - gap; // j 代表i的上一个元素，相差一个增量gap。
// j < 0 时退出循环，说明 j 是最小的元素的索引值。
// 或者 arr[j] <= value 时退出循环，说明 j 是比value小的元素的索引值。
for (; j >= 0 && arr[j] > value; j -= gap) {
arr[j + gap] = arr[j]; // 把元素往后挪。
}
arr[j + gap] = value;
}
// 把每一趟排序的结果也输出一下。
print(arr);
// 缩小增量。
gap /= 2;
}
}
public static void main(String[] args) {
int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};
System.out.print("排序前: ");
print(arr);
shellSort(arr);
System.out.print("排序后: ");
print(arr);
}
// 打印数组
public static void print(int[] arr) {
if (arr == null) return;
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
/*
排序前: 6 9 1 4 5 8 7 0 2 3
6 7 0 2 3 8 9 1 4 5
0 1 3 2 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
排序后: 0 1 2 3 4 5 6 7 8 9
*/ 9、堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
/**
* 堆排序
* @param array
*/
public static void HeapSort(int[] array){
for(int i=0;i<array.length-1;i++){
//建堆
buildMaxHeap(array,array.length-1-i);
//交换堆顶和最后一个元素
swap(array,0,array.length-1-i);
}
System.out.println(Arrays.toString(array));
}
public static void buildMaxHeap(int[] data,int lastIndex){
//从lastIndex处节点（最后一个节点）的父节点开始
for(int i = (lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k = i;
//如果k节点的子节点存在
while(k*2+1<=lastIndex){
//将k点左子节点的索引赋值给biggerIndex
int biggerIndex = 2*k+1;
//如果biggerIndex小于lastIndex，代表k节点的右子节点存在
if(biggerIndex < lastIndex){
//如果右子节点的值较大
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大子节点的值
if(data[k] < data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
private static void swap(int[] data,int i,int j){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
} 10、归并排序
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
/**
* 归并排序
* @param array
*/
public static void mergingSort(int[] array) {
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array) + " mergingSort");
}
private static void sort(int[] data, int left, int right) {
if (left < right) {
//找出中间索引
int center = (left + right) / 2;
//对左边数组进行递归
sort(data, left, center);
//对右边数组进行递归
sort(data, center + 1, right);
//合并
merge(data, left, center, right);
}
}
private static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int mid = center + 1;
//third记录中间数组的索引
int third = left;
int tmp = left;
while (left <= center && mid <= right) {
//从两个数组中取出最小的放入中间数组
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
//剩余部分依次放入中间数组
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
//将中间数组中的内容复制回原数组
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
} 
京公网安备 11010502036488号