本文以列举java中比较常见的几种排序：冒泡排序、快速排序、插入排序、希尔排序、选择排序、归并排序以及基数排序。
冒泡排序
/**
* @author fandongfeng
* @created 2020/1/9 17:08
* @description 冒泡排序
* 两两比较，大的右移，比出最大的，然后重新开始比
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[] {5,7,2,9,4,1,0,5,7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
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;
}
}
}
}
}
快速排序
/**
* @author fandongfeng
* @created 2020/1/9 17:08
* @description 快速排序
* 开始位置，结束位置，以第一个数作为标准，比标准大的放到左边，比标准大的放到右边，然后递归标准数位置左右两边的数组就OK了
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end) {
if(start < end) {
//把第0个做为标准
int stard = arr[start];
//记录需要排序的下标
int low = start;
int high = end;
//循环找比标准数大的数
while(low<high) {
//右边比标准大
while(low<high && stard <= arr[high]){
high--;
}
//使用右边数字替换左边数字
arr[low]=arr[high];
//如果左边数字比标准数字小
while(low<high && arr[low]<=stard){
low++;
}
arr[high] = arr[low];
}
//把标准数赋给低所在的位置的元素
arr[low] = stard;
//处理所有的比标准数小的数字
quickSort(arr, start, low-1);
//处理所有的比标准数大的数字
quickSort(arr, low+1, end);
}
}
}
插入排序
/**
* @author fandongfeng
* @created 2020/1/9 20:11
* @description 插入排序
* 默认该位置左边都是排好序的，所以只要和左边比较
* 如果小于左边，则此值赋给临时变量，左边值赋给当前（左边位置+1），继续向左与临时变量比较，小于继续赋值给该位置+1处，
* 不满足则将临时变量赋给不满足位置+1处
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void insertSort(int[] arr) {
//遍历所有数字
for (int i = 1; i < arr.length; i++) {
//如果当前数字比前一个小
if(arr[i] < arr[i-1]){
int temp = arr[i];
//遍历当前数字前面的所有数字
int j;
for (j = i-1; j >=0 && temp < arr[j]; j--) {
//把前一个数字赋给后一个数字
arr[j+1] = arr[j];
}
//把临时变量赋给不满足条件的后一个元素
arr[j+1] = temp;
}
}
}
}
希尔排序
/**
* @author fandongfeng
* @created 2020/1/9 20:41
* @description 希尔排序
* 长度/2 相隔相同步长的元素进行插入排序 长度/2/2 依次进行
* 优点，将比较小的元素快速排到前面
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void shellSort(int[] arr) {
//遍历所有步长
for (int d = arr.length/2; d > 0; d/=2) {
//遍历所有元素
for (int i = d; i < arr.length; i++) {
//遍历本组中所有元素
for (int j = i-d; j >= 0; j-=d) {
//如果当前元素大于加上步长后的那个元素
if(arr[j] > arr[j+d]){
int temp = arr[j];
arr[j] = arr[j+d];
arr[j+d] = temp;
}
}
}
}
}
}
选择排序
/**
* @author fandongfeng
* @created 2020/1/13 15:21
* @description 选择排序
* 遍历找出最小元素放在第一位，遍历找第二个...
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void selectSort(int[] arr) {
//遍历
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
//
for (int j = i+1; j < arr.length; j++) {
if(arr[minIndex] > arr[j]) {
//记录最小坐标
minIndex = j;
}
}
//不相等则交换
if(i != minIndex) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
归并排序
/**
* @author fandongfeng
* @created 2020/1/13 15:43
* @description 归并排序
* 先拆分成两个有序数组
* 然后两个数组合并
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[] {1,3,5,2,4,6,8,10};
mergeSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
/**
* 将一个数组分成两个有序数组
* 左右两边各递归出来两个有序数组，在进行合并
*/
public static void mergeSort(int[] arr, int low, int high) {
int middle = (low + high)/2;
if(low < high) {
//处理左边
mergeSort(arr, low, middle);
//处理右边
mergeSort(arr, middle+1, high);
//归并
merge(arr, low, middle, high);
}
}
public static void merge(int[] arr, int low, int middle, int high) {
/**
* ----------arr = [1, 3, 5, 2, 4, 6, 8, 10], low = 0, middle = 0, high = 1
* ----------arr = [1, 3, 5, 2, 4, 6, 8, 10], low = 2, middle = 2, high = 3
* ----------arr = [1, 3, 2, 5, 4, 6, 8, 10], low = 0, middle = 1, high = 3
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 4, middle = 4, high = 5
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 6, middle = 6, high = 7
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 4, middle = 5, high = 7
* ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 0, middle = 3, high = 7
*
* [1, 2, 3, 4, 5, 6, 8, 10]
*/
System.out.println("----------arr = "+ Arrays.toString(arr)+", low = " + low + ", middle = " + middle + ", high = " + high);
//用于存储归并后的临时数组
int[] temp = new int[high-low+1];
//记录第一个数组中需要遍历的下标
int i = low;
//记录第二个数组中需要遍历的下标
int j = middle + 1;
//用于记录在临时数组中存放的下标
int index = 0;
//遍历两个数组，取出小的数字，放入临时数组中
while (i<=middle && j<=high) {
if(arr[i] <= arr[j]) {
temp[index] = arr[i];
i++;
}else {
temp[index] = arr[j];
j++;
}
index ++;
}
//处理多余的数据
while (j <= high) {
temp[index] = arr[j];
j++;
index++;
}
while (i <= middle) {
temp[index] = arr[i];
i++;
index++;
}
//把临时数组数据重新存入原数组
for (int k = 0; k < temp.length; k++) {
arr[k+low] = temp[k];
}
}
}
基数排序
/**
* @author fandongfeng
* @created 2020/1/13 18:57
* @description 基数排序
*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = new int[]{23,6,189,45,9,287,56,1,798,34,65,652,5};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 假设有0,1,2,3,4,5,6,7,8,9 十个桶，
* 获得最大数字位数轮询
* 按个位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字
* 按十位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字
* ...
* @param arr
*/
private static void radixSort(int[] arr) {
//存取数组最大数
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
//最大数字位数
int maxLength = (max+"").length();
//存储临时的数据数组
int[][] temp = new int[10][arr.length];
//用于记录temp中同一列存放数字个数
int[] count = new int[10];
//根据最大长度数决定比较次数
for (int i=0, n=1; i < maxLength; i++,n*=10) {
//把每一个数字分别计算余数
for (int j = 0; j < arr.length; j++) {
//余数
int ys = arr[j] / n % 10;
//存到相应的数组中
temp[ys][count[ys]] = arr[j];
//记录数量
count[ys]++;
}
//记录取的元素需要放的位置
int index = 0;
//把数字取出来
for (int k = 0; k < count.length; k++) {
if(count[k] != 0) {
//循环取出元素
for (int l = 0; l < count[k]; l++) {
arr[index] = temp[k][l];
index++;
}
//把数量置为0
count[k] = 0;
}
}
}
}
}
既然是FIFO的排序，则可以用队列代替
/**
* @author fandongfeng
* @created 2020/1/13 18:57
* @description 基数排序 - 基于队列（FIFO）实现
*/
public class RadixQueueSort {
public static void main(String[] args) {
int[] arr = new int[]{23,6,189,45,9,287,56,1,798,34,65,652,5};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 假设有0,1,2,3,4,5,6,7,8,9 十个桶，
* 获得最大数字位数轮询
* 按个位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字
* 按十位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字
* ...
* @param arr
*/
private static void radixSort(int[] arr) {
//存取数组最大数
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
//最大数字位数
int maxLength = (max+"").length();
//存储临时的数据队列
Queue[] temp = new LinkedBlockingQueue[10];
//初始化，防止NPE报错
for (int i = 0; i < temp.length; i++) {
temp[i] = new LinkedBlockingQueue();
}
//根据最大长度数决定比较次数
for (int i=0, n=1; i < maxLength; i++,n*=10) {
//把每一个数字分别计算余数
for (int j = 0; j < arr.length; j++) {
//余数
int ys = arr[j] / n % 10;
//存到指定队列
temp[ys].add(arr[j]);
}
//记录取的元素需要放的位置
int index = 0;
//把数字取出来
for (int k = 0; k < temp.length; k++) {
if(!temp[k].isEmpty()) {
//循环取出元素
while (!temp[k].isEmpty()) {
arr[index] = Integer.valueOf(temp[k].poll()+"");
index++;
}
}
}
}
}
}
堆排序
/**
* @author fandongfeng
* @created 2020/1/14 17:58
* @description 堆排序
* 堆排序：
* 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
* 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：
* 即子结点的键值或索引总是小于（或者大于）它的父节点
*
* 堆排序的基本思想是：将待排序序列构造成一个大顶堆，
* 此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。
* 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
* 如此反复执行，便能得到一个有序序列了
* 一般升序采用大顶堆，降序采用小顶堆
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[] {9,6,8,7,0,1,10,4,2};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] arr) {
//最后一个非叶子节点
int start = arr.length/2 -1;
//调整成大顶堆
for (int i = start; i >= 0; i--) {
maxHeap(arr, arr.length, i);
}
//先把数组的第0个和堆中最后一个交换位置， 在把前面的处理为大顶堆
for (int i= arr.length -1; i>0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeap(arr, i, 0);
}
}
/**
* 数组转成大顶堆
*/
private static void maxHeap(int[] arr, int size, int index) {
//左子节点
int leftNode = 2*index + 1;
//右子节点
int rightNode = 2*index + 2;
int max = index;
//和两个子节点分别对比，找出最大的节点
if(leftNode < size && arr[leftNode] > arr[max]) {
max = leftNode;
}
if(rightNode < size && arr[rightNode] > arr[max]) {
max = rightNode;
}
//交换位置
if(max != index) {
int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
//交换之后，可能会破坏之前排好的序
maxHeap(arr, size, max);
}
}
}
image.png
