1. 排序概述
2. 排序实现
2.1 冒泡排序
2.2 快速排序
2.2 直接插入排序
2.2 希尔排序
2.2 简单选择排序
2.2 堆排序
2.2 归并排序
2. 代码实现
package com.zrj.algorithm.sort;
import com.alibaba.fastjson.JSON;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 排序算法
*
* @author zrj
* @date 2021/8/29
* @since V1.0
**/
public class SortData {
public static void main(String[] args) {
int[] array = {2, 5, 3, 1, 4};
bubbleSort( array );
insertSort( array );
hillSort( array );
selectSort( array );
quickSort( array, 0, array.length - 1 );
}
/**
* 冒泡排序
*/
public static void bubbleSort(int[] array) {
for (int i = array.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
// 如果array[j]>array[j+1]，交换位置
if (array[j] > array[j + 1]) {
int variable = array[j];
array[j] = array[j + 1];
array[j + 1] = variable;
}
}
}
System.out.println( "冒泡排序：" + JSON.toJSONString( array ) );
}
/**
* 快速排序
*/
public static void quickSort(int[] array, int left, int right) {
int low = left;
int high = right;
if (low > high) {
return;
}
// 取数组第一个数k作为衡量标准
int k = array[low];
while (low < high) {
// 右侧找到第一个小于k的停止
while (low < high && array[high] >= k) {
high--;
}
// 找到第一个比k小的数，放在low的位置
array[low] = array[high];
//找到第一个大于k的值停止
while (low < high && array[low] <= k) {
low++;
}
array[high] = array[low];
}
//赋值，然后左右递归
array[low] = k;
quickSort( array, left, low - 1 );
quickSort( array, low + 1, right );
System.out.println( "快速排序：" + JSON.toJSONString( array ) );
}
/**
* 直接插入排序
*/
public static void insertSort(int[] array) {
int variable;
for (int i = 0; i < array.length; i++) {
variable = array[i];
for (int j = i - 1; j >= 0; j--) {
if (array[j] > variable) {
array[j + 1] = array[j];
array[j] = variable;
} else {
break;
}
}
}
System.out.println( "直接插入排序：" + JSON.toJSONString( array ) );
}
/**
* 希尔排序
*/
public static void hillSort(int[] array) {
int d = array.length;
//临时变量
int variable;
//共分成d组
for (; d >= 1; d /= 2) {
//到那个元素就看这个元素在的那个组即可
for (int i = d; i < array.length; i++) {
variable = array[i];
for (int j = i - d; j >= 0; j -= d) {
if (array[j] > variable) {
array[j + d] = array[j];
array[j] = variable;
} else {
break;
}
}
}
}
System.out.println( "希尔排序：" + JSON.toJSONString( array ) );
}
/**
* 简单选择排序
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i; // 最小位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j; // 更换最小位置
}
}
if (min != i) {
swap( arr, i, min ); // 与第i个位置进行交换
}
}
System.out.println( "简单选择排序：" + JSON.toJSONString( arr ) );
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 堆排序
* 下移交换 把当前节点有效变换成一个堆(小根)
*/
static void shiftDown(int arr[], int index, int len) {
//0 号位置不用
int leftchild = index * 2 + 1;//左孩子
int rightchild = index * 2 + 2;//右孩子
if (leftchild >= len) {
return;
} else if (rightchild < len && arr[rightchild] < arr[index] && arr[rightchild] < arr[leftchild]) {
//右孩子在范围内并且应该交换
swap( arr, index, rightchild );//交换节点值
shiftDown( arr, rightchild, len );//可能会对孩子节点的堆有影响，向下重构
} else if (arr[leftchild] < arr[index]) {
//交换左孩子
swap( arr, index, leftchild );
shiftDown( arr, leftchild, len );
}
}
static void creatHeap(int arr[]) {
//将数组创建成堆
for (int i = arr.length / 2; i >= 0; i--) {
shiftDown( arr, i, arr.length );
}
}
static void heapSort(int arr[]) {
System.out.println( "原始数组为：" + Arrays.toString( arr ) );
int val[] = new int[arr.length]; //临时储存结果
//step1建堆
creatHeap( arr );
System.out.println( "建堆后的序列为：" + Arrays.toString( arr ) );
//step2 进行n次取值建堆，每次取堆顶元素放到val数组中，最终结果即为一个递增排序的序列
for (int i = 0; i < arr.length; i++) {
val[i] = arr[0];//将堆顶放入结果中
arr[0] = arr[arr.length - 1 - i];//删除堆顶元素，将末尾元素放到堆顶
shiftDown( arr, 0, arr.length - i );//将这个堆调整为合法的小根堆，注意(逻辑上的)长度有变化
}
//数值克隆复制
for (int i = 0; i < arr.length; i++) {
arr[i] = val[i];
}
System.out.println( "堆排序后的序列为:" + Arrays.toString( arr ) );
}
/**
* 归并排序
*/
private static void mergesort(int[] array, int left, int right) {
int mid = (left + right) / 2;
if (left < right) {
mergesort( array, left, mid );
mergesort( array, mid + 1, right );
merge( array, left, mid, right );
}
}
private static void merge(int[] array, int l, int mid, int r) {
int lindex = l;
int rindex = mid + 1;
int team[] = new int[r - l + 1];
int teamindex = 0;
while (lindex <= mid && rindex <= r) {//先左右比较合并
if (array[lindex] <= array[rindex]) {
team[teamindex++] = array[lindex++];
} else {
team[teamindex++] = array[rindex++];
}
}
//当一个越界后剩余按序列添加即可
while (lindex <= mid) {
team[teamindex++] = array[lindex++];
}
while (rindex <= r) {
team[teamindex++] = array[rindex++];
}
for (int i = 0; i < teamindex; i++) {
array[l + i] = team[i];
}
}
/**
* 桶排序
*/
public static void bucketSort() {
int a[] = {1, 8, 7, 44, 42, 46, 38, 34, 33, 17, 15, 16, 27, 28, 24};
List[] buckets = new ArrayList[5];
//初始化
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<Integer>();
}
//将待排序序列放入对应桶中
for (int i = 0; i < a.length; i++) {
int index = a[i] / 10;//对应的桶号
buckets[index].add( a[i] );
}
//每个桶内进行排序(使用系统自带快排)
for (int i = 0; i < buckets.length; i++) {
buckets[i].sort( null );
for (int j = 0; j < buckets[i].size(); j++)//顺便打印输出
{
System.out.print( buckets[i].get( j ) + " " );
}
}
}
/**
* 计数排序
*/
public static void countSort(int[] a) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
//找到max和min
for (int i = 0; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
int[] count = new int[max - min + 1];//对元素进行计数
for (int i = 0; i < a.length; i++) {
count[a[i] - min]++;
}
//排序取值
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i]-- > 0) {
a[index++] = i + min;//有min才是真正值
}
}
}
/**
* 基数排序
*/
public static void radixSort(int[] arr) {
{
List<Integer>[] bucket = new ArrayList[10];
for (int i = 0; i < 10; i++) {
bucket[i] = new ArrayList<>();
}
//找到最大值
int max = 0;//假设都是正数
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int divideNum = 1;//1 10 100 100……用来求对应位的数字
while (max > 0) {//max 和num 控制
for (int num : arr) {
bucket[(num / divideNum) % 10].add( num );//分配 将对应位置的数字放到对应bucket中
}
divideNum *= 10;
max /= 10;
int idx = 0;
//收集 重新捡起数据
for (List<Integer> list : bucket) {
for (int num : list) {
arr[idx++] = num;
}
list.clear();//收集完需要清空留下次继续使用
}
}
}
}
}