五种排序
常见的排序算法有十种：
-
三大基础排序：选择、冒泡、插入（时间复杂度：O(n^2)，空间复杂度（O(1)）比较低）使用的是最基本的两层嵌套结构
-
快速、归并、堆、希尔、桶、计数、基数
-
排序：1）升序：从小到大
2）降序：从大到小
1、冒泡排序法
冒泡排序是一种简单排序算法，它通过以此比较交换两个相邻元素实现功能。每一次冒泡会让至少一个元素移动到它应该在的位置上，这样n次冒泡就完成了n个数据的排序工作。
冒泡排序算法实现步骤：
-
比较相邻的元素，如果第一个比第二个大，就交换它们两个。
-
对每一对相邻元素重复上述工作，从第一对到最后一对。完成后，最大的数会放到最后位置。
-
针对所有的元素重复以上的步骤，除了最后一个
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
-
简单来说就是：比较相邻的元素，如果第一个比第二个大，就交换他们两个。
package com.briup.chap04.sorted;
import java.util.Arrays;
/**
* 冒泡排序法
*/
public class BubbleSort2 {
public static void main(String[] args) {
int[] arr = {7, 4, 1, 2, 9, 6, 5, 8};
bubbleSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
}
//冒泡排序法(次案例从小到大排序）
public static void bubbleSort(int[] arr){
//整体结构两层嵌套循环
//外循环：完成整体排序，执行一轮：找到一个当前最大值放置在正确位置
//内循环：执行一轮：完成一次相邻两元素的比较和交换
for (int i = 0; i < arr.length - 1; i++) {
//两两交换，把最大的数放在最后
//第一轮：i=0; length-1
//第二轮：i=1; length-2
//第三轮：i=2; length-3
for (int j = 0; j < arr.length - i - 1; j++){
if (arr[j] > arr[j + 1]){
//进行交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.print("第"+(i+1)+"次排序后: ");
System.out.println(Arrays.toString(arr));
}
}
}
2、二分查找
在一个有序序列中查找其中某个元素，采用二分查找（折半查找）。
基本思想：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x = a[n/2]则找到x，算法终止；如果x < a[n/2]，则我们只要在数组a的左半部分继续搜索x；如果x > a[n/2]，则我们只要在数组a的有半部继续搜索x。
package com.briup.chap04.sorted;
/**
* 二分查找
*/
public class binarySearch {
// 二分查找：针对有序序列进行 查找
public static void main(String[] args) {
int[] arr = {1, 3, 4, 5, 7, 9, 10};
int index = binarySearch(arr, 1);
System.out.println("index(1) = " + index);
index = binarySearch(arr, 5);
System.out.println("index(5) = " + index);
index = binarySearch(arr, 10);
System.out.println("index(10) = " + index);
}
//二分查找算法，如果value存在arr中，则返回元素位置，如果找不到返回-1
public static int binarySearch(int[] arr, int value){
int start = 0;
int end = arr.length - 1;
int mid;
while (true){
mid = (start + end) / 2;
if (value == arr[mid]){
return mid;
}else if (value > arr[mid]){
start = mid + 1;
}else{
end = mid - 1;
}
//当start > end 循环结束
if (start > end){
break;
}
}
return -1;
}
}3、选择排序
选择排序的原理有点类似于插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾，最终完成排序。
选择排序算法描述：
-
初始状态：无序区间为Arr[0,1...n]，有序区间为空；
-
第i==1趟排序开始，从无序区中选出最小的元素Arr[k]，将它与无序区的第1个元素交换，从而得到有序区间Arr[0...i-1]，无序区间Arr[i...n]；
-
继续后面第i趟排序（i=2，3...n-1），重复上面第二步过程；
-
第n-1趟排序结束，数组排序完成。
package com.briup.chap04.sorted;
import java.util.Arrays;
/**
* 选择排序
*/
public class SelectSort2 {
public static void main(String[] args) {
//定义要排序的数组
int[] arr = {7, 4, 1, 2, 9, 6, 5, 8};
//调用方法完成排序
sort(arr);
//打印输出排序后的结果
print(arr);
}
//对数组进行排序
public static void sort(int[] arr){
/**
* 两层循环嵌套结构
* 外循环：负责整体排序的实现，执行一轮就表示排好了一个数
* 内循环：负责找出一个当前无序区的最大值
* 执行一轮表示完成了一次两数值之间的大小比较
*/
for (int i = 0; i < arr.length; i++) {
//数组长度为8
//第一轮外循环i=0，内循环次数为7，最后一个比较的元素length-0-1
//第二轮外循环i=1，内循环次数为6，最后一个比较的元素length-1-1
//第三轮外循环i=2，内循环次数为5，最后一个比较的元素length-2-1
//内循环次数：length-i-1
int maxIndex = 0;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[maxIndex]){
maxIndex = j;
}
}
// 把maxIndex和另外一个位置元素进行交换
// i=0，length-1
// i=1，length-2
swap(arr,maxIndex,arr.length - i - 1);
print(arr); //每一次交换之后打印输出数组
}
}
//对数组元素进行打印输出的方法
public static void print(int[] arr){
System.out.println(Arrays.toString(arr));
}
//用于交换指定数组中的两元素位置
public static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// 如果一定要使用不借助中间变量的方法，完成交换，
// 一定要判断i和j的值是否相等（如果相等则不进行交换）
// if (i != j) {
// arr[i] = arr[i] + arr[j];
// arr[j] = arr[i] - arr[j];
// arr[i] = arr[i] - arr[j];
// }
}
}
4、插入排序
插入排序，一般也被称为直接插入排序，对于少量元素的排序，它是一个有效的算法。
插入排序算法描述：
-
将数组分成两部分，已排序、未排序区间，初始情况下，已排序区间只有一个元素，即数组第一个元素；
-
取未排序区间中第一个元素，插入到已排序区间中合适的位置，这样子就得到了一个更大的已排序区间；
-
重复这个过程，直到未排序区间中元素为空，算法结束
public class InsertionSort2 {
public static void main(String[] args) {
// 要排序的数组
int[] arr = {7, 4, 1, 2, 9, 6, 5, 8};
// 调用方法进行排序
sort(arr);
// 打印排序后的结果
print(arr);
}
// 对数组进行排序
public static void sort(int[] arr){
// 外循环控制总体循环次数
for (int i = 1; i < arr.length; i++) {
// 内循环：将arr[i]以此与左边[0, i-1]（有序区）范围内的牌进行比较
// 如果小于左边的牌, 就交换位置，或者已经被交换到了[0]位置则停止（j>0）
int j = i;
// [j]和[j-1]是每次都要比较的两个牌位置，j初始为i，第一轮j-1为当前有序区最大值
while (j > 0 && arr[j] < arr[j - 1]){
swap(arr, j, --j);
}
}
}
//打印数组
public static void print(int[] arr){
System.out.println(Arrays.toString(arr));
}
// 交换指定数组中两元素的位置
public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
5、希尔排序
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2)的第一批算法之一。
希尔排序对直接插入排序改进的着眼点：
-
若待排序序列中元素基本有序时，直接插入排序的效率可以大大提高
-
如果待排序序列中元素数量较小时，直接插入排序效率很高
希尔排序算法思路：
将整个待排序序列分割成若干个子序列，在子序列内部分别进行直接插入排序，等到整个序列基本有序时，再对全体成员进行直接插入排序。
待解决问题：
-
如何分割子序列，才能保证最终能得到基本有序？
-
子序列内部如何进行直接插入排序？
分割方案：
-
将有n个元素的数组分成n/2个数字序列，第i个元素和第i+n/2，i+n/2*m...个元素为一组；
-
对一组数列进行简单插入排序；
-
然后，调整增量为n/4，从而得到新的几组数列，再次排序；
-
不断重复上述过程，直到增量为1，希尔排序完全转化成简单插入排序，完成该趟排序，则数组排序成功。
/**
* 希尔排序
*
* Gap的取值：总体来讲，只要体现出Gap由大到小递减，最终必然为1的结果，就是可取的。
*
* 工程上Gap数列的选择，一般会有两种方式：
* 1、shell数列：取所有的2^n-1
* 1、3、7、15、31、63、127...
* 二进制：1个1、2个1、3个1...
*
* 2、Knuth序列（克努特）
* 规律3n + 1序列
* 1、4、13、40、121
* @author 35329
*/
public class ShellSort {
public static void main(String[] args) {
// 要排序的数组
int[] arr = {7, 4, 1, 2, 9, 6, 5, 8};
// 调用方法进行排序
sort(arr);
// 打印排序后的结果
print(arr);
}
public static int nextGap(int gap){
return (gap - 1) / 3;
}
public static int gap(int[] arr){
// 根据数组的长度取首个gap值
int length = arr.length;
int gap = 1;
while (gap * 3 + 1 < length){
gap = gap * 3 + 1;
}
return gap;
}
public static void sort(int[] arr){
/**
* 三层循环
* 最外层：Gap的变化
* 中间层：原来插入排序的外层，排好一组序
* 最内层：原来插入排序的内存，完成比较
*/
for (int gap = 4; gap >= 1; gap /= 2){
// i=gap等同于普通插入排序的int i = 1
for (int i = gap; i < arr.length; i++){
//1、当前位置已经不小于左边位置的值
//2、索引值已经小于gap了
int j = i;
while (j >= gap && arr[j] < arr[j - gap]){
// 借助直插思想，发现大于目标元素的，仅做右移操作
// 最终循环结束之后，j指向的位置就是新元素应该插入的位置，直接一次性插入即可
swap(arr, j, j - gap);
j -= gap;
}
}
}
}
//打印数组
public static void print(int[] arr){
System.out.println(Arrays.toString(arr));
}
// 交换指定数组中两元素的位置
public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}