Java 数组排序

目录

1.Java冒泡排序（Bubble Sort）

1.冒泡排序

2.冒泡排序的算法原理

3.冒泡排序的复杂度和性能

4.形成代码

2.Java快速排序（Quick Sort）

3.Java归并排序（Merge Sort）

4.Java选择排序（Selection Sort）

5.Java直接插入排序

6.Java希尔排序（Shell Sort）

---

1.Java冒泡排序（Bubble Sort）

1.冒泡排序

冒泡排序（Bubble Sort）是编程中较简单的一种排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误，就把它们交换过来。重复地进行走访数列的工作直到没有再需要交换的元素，这也就意味着该数列已经完成排序。

冒泡排序就像气泡从水中出现一样，在气泡排序中最小或最大的数字，取决于我们是按升序还是降序排序数组，气泡朝着数组的开始或结束冒出。

2.冒泡排序的算法原理

1）比较相邻的元素，如果第一个比第二个大，就交换他们两个。

2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，在这一点，最后的元素应该会是最大的数。

3）针对所有的元素重复以上的步骤，除了最后一个。

4）持续对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.冒泡排序的复杂度和性能

与其他排序算法，诸如快速排序、归并排序或shell排序相比，冒泡排序表现不佳。这些算法的平均情况复杂度为O(nlogn)，而冒泡排序平均情况复杂度为O(n^2)。

在最佳情况下，冒泡排序比具有O(n)性能的快速排序更好。冒泡排序比快速排序或归并排序慢三倍，即使n=100，但它更容易实现和记忆。

冒泡排序的复杂度和性能如下：

1）冒泡排序最差情况性能O(n^2)

2）冒泡排序最佳情况性能O(n)

3）冒泡排序平均情况性能O(n^2)

4.形成代码

//冒泡排序
public static void bubbleSort(int[] arr) {//外层循环用来控制数组循环的圈数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;}}}//输出结果for(int n:nums) {System.out.println(n);}
}

例如：

public class Main {public static void main(String[] args) {int a[] = {6,1,15,32,9};for(int i=1;i<a.length;i++) {for(int j=0;j<a.length-1;j++) {if(a[j] > a[j+1]) {int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}System.out.println("冒泡排序的结果是：");for(int temp:a) {System.out.print(temp+" ");}}
}

运行结果如下：

冒泡排序的结果是：
1 6 9 15 32

2.Java快速排序（Quick Sort）

快速排序（Quick Sort）是基于二分思想，对冒泡排序的一种改进。主要思想是确立一个基数，将小于基数的数字放到基数的左边，大于基数的数字放到基数的右边，然后再对这两部分数字进一步排序，从而实现对数组的排序。

其优点是效率高，时间复杂度平均为O(nlogn)，顾名思义，快速排序是最快的排序算法，耗费的资源少，最佳情况下，空间复杂度为O(logn)，每一次都平分数组的情况，代码较为简单。

其缺点是不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。

例如：

public class Main {//快排实现方法public static void quickRow(int[] array,int low,int high) {int i,j,pivot;//结束条件if(low >= high) {return;}i = low;j = high;//选择的节点，这里选择的数组的第一数作为节点pivot = array[low];while(i<j) {//从右往左找比节点小的数，循环结束要么找到了，要么i=jwhile(array[j] >= pivot && i<j) {j--;}//从左往右找比节点大的数，循环结束要么找到了，要么i=jwhile(array[i] <= pivot && i<j) {i++;}//如果i!=j说明都找到了，就交换这两个数if(i<j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}//i==j一轮循环结束，交换节点的数和相遇点的数array[low] = array[i];array[i] = pivot;//数组“分两半”,再重复上面的操作quickRow(array,low,i-1);quickRow(array,i+1,high);}public static void main(String[] args) {int[] array = {6,17,38,59,2,10};int low = 0,high = array.length-1;quickRow(array,low,high);for (int i : array){System.out.println(i);}}
}

运行结果如下：

2
6
10
17
38
59

3.Java归并排序（Merge Sort）

归并排序（Merge Sort）是建立在归并操作上的一种有效的稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序将两个有序的子序列合并得到一个完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序的列表合并成一个有序的列表，我们称之为二路归并。

归并排序的速度仅次于快速排序，时间复杂度为O(nlogn)。其拆分过程中使用了二分思想，是一个递归的过程，为了减少在递归过程中不断开辟空间的问题，我们可以在归并排序之前，先开辟出一个临时空间，在递归过程中统一使用此空间进行归并即可。

例如：

import java.util.Arrays;
public class Main {public static void main(String[] args) {int[] arr = new int[]{86,23,7,45,19,10};int left = 0;int right = arr.length-1;int[] tem = Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,right,tem);print(arr);}public static void mergeSort(int[] arr,int left,int right,int[] tem) {if(right-left<1) {return;}int mid = left + (right-left)/2;mergeSort(arr,left,mid,tem);mergeSort(arr,mid+1,right,tem);merge(arr,left,mid,right,tem);}private static void merge(int[] arr,int left,int mid,int right,int[] tem) {int index = 0;int l = left,r = mid+1;while(l <= mid && r <= right) {if(arr[l]<arr[r]) {tem[index++] = arr[l++];}else{tem[index++] = arr[r++];}}while(l <= mid) {tem[index++] = arr[l++];}while(r <= right) {tem[index++] = arr[r++];}for(int i=0;i<(right-left+1);i++) {arr[left+i] = tem[i];}}private static void print(int[] arr) {for (int i : arr) {System.out.print(i+"\t");}System.out.println();}
}

运行结果如下：

86  23  7   45  19  10 
7   10  19  23  45  86

4.Java选择排序（Selection Sort）

选择排序（Selection Sort）是一种简单直观的排序算法，其算法原理为首先在未排序的序列中找到最小（大）的元素，存放到排序序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（大）的元素，存放到已排序序列的末尾，以此类推，直到所有元素均排序完成。

选择排序一共有“数组数-1”轮排序，每一轮排序又是一个循环，循环的规则如下：

1）先假定当前这轮循环的第一个数是最小数。

2）然后和后面每个数进行比较，如果发现有比当前数更小的数，则重新确定最小数，并得到下标。

3）当遍历到数组的最后时，就得到本轮最小的数。

4）和当前循环的第一个数进行交换。

例如：

import java.util.Arrays;
public class Main {public static void main(String[] args) {int[] arr = new int[]{19,26,8,35,41,77};for(int i=0;i<arr.length-1;i++) { //每次循环都会找出最小的数int minIndex = i; //记录最小数的下标int minNum = arr[i]; //记录最小数for(int j=i+1;j<arr.length;j++) { //每次循环都会找出最小的数if(arr[j]<minNum) { //如果当前数比最小数小，则更新最小数minNum = arr[j]; //更新最小数minIndex = j; //更新最小数的下标}}arr[minIndex] = arr[i]; //将最小数放到最前面arr[i] = minNum; //将标志位放到最小数原来所在的位置}for(int i=0;i<arr.length;i++) {System.out.println(arr[i]);}}
}

运行结果如下：

8
19
26
35
41
77

5.Java直接插入排序

直接插入排序是指将一个个待排序的元素插入到前面已经排好序的有序序列中去，直到插完所有元素为止，主要步骤如下：

1）先假设第一个元素已经排好序。

2）然后依次取出还需要进行排序的下一个元素，也就是排序完成的元素后面的下一个元素，取出下一个元素，设为待插入元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。

3）重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素。

4）重复步骤2、步骤3，完成排序。

例如：

import java.util.Arrays;
public class Main {public static void main(String args[]) {int[] arr = new int[]{17,62,39,52,8,24};for(int i=1;i<arr.length;i++) { //从第二个元素开始比较int temp = arr[i]; //记录当前元素for(int j=i-1;j>=0;j--) { //从最后一个元素开始比较if(arr[j]>temp) { //如果比当前元素大arr[j+1] = arr[j]; //从该处往后所有元素向后移动一位arr[j] = temp; //将当前元素插入到arr[j]中}}}for(int i=0;i<arr.length;i++) {System.out.print(arr[i]+" ");}}
}

运行结果如下：

8 17 24 39 52 62

6.Java希尔排序（Shell Sort）

希尔排序（Shell Sort）是插入排序的一种，也是直接插入排序的更高效的改进版本，希尔排序充分利用了插入排序的两个特点：

1）当数据规模小的时候非常高效。

2）当给定数据已经有序时的时间复杂度为O(n)。

所以，Shell排序每次把数据分成若干块，来使用插入排序，而且之后在这若干个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停地合并小块，直到最后一个小块。

这里每次分成若干个小块是通过“增量”来控制的，开始的时候增量较大，接近n/2，从而使得分割出来接近n/2个小块，逐渐的减小“增量”，最终减小到1。

例如：

public class Main {public static int count = 0;public static void shellSort(int[] data) {// 计算出最大的h值int h = 1;while(h <= data.length / 3) {h = h * 3 + 1;}while(h > 0) {for(int i=h;i<data.length;i+=h) {if(data[i] < data[i-h]) {int tmp = data[i];int j = i-h;while(j >= 0 && data[j] > tmp) {data[j+h] = data[j];j -= h;}data[j+h] = tmp;print(data);}}// 计算出下一个h值h = (h - 1) / 3;}}public static void print(int[] data) {for(int i=0;i< data.length;i++) {System.out.print(data[i]+"\t");}System.out.println();}public static void main(String[] args) {int[] data = new int[]{4,6,1,9,5,8};print(data);shellSort(data);print(data);}
}

运行结果如下：

4   6   1   9   5   8  
1   4   6   9   5   8  
1   4   5   6   9   8  
1   4   5   6   8   9  
1   4   5   6   8   9