动图来源：
参考链接
参考链接
1.冒泡排序
package 排序;
import java.util.Arrays;
public class 冒泡排序 {
public static void main(String[] args) {
int [] arr = new int[]{7,8,9,2,1,5,9,4,4,5,6};
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;
}
}
}
}
}2.选择排序
package 排序;
import java.util.Arrays;
public class 选择排序 {
public static void main(String[] args) {
int [] arr = new int[]{7,8,9,2,1,5,9,4,4,5,6};
for (int i=0;i<arr.length-1;i++){
int index = i;//需要比较的数 arr[index]
System.out.println(i);
for (int j=i+1;j<arr.length;j++){
if (arr[j]<arr[index]){
index= j;//保存最小元素的小标，成为带比较的数字
}
}
//找到最小值，将其放在本轮比较的开头，进行下一遍循环。
int temp = arr[index];
arr[index]=arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
}3.插入排序
package 排序;
import java.util.Arrays;
public class 插入排序 {
public static void main(String[] args) {
int [] arr = new int []{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
for (int i = 0;i<arr.length;i++){
int Instertvalue = arr[i];
int Instertindex = i-1;
while(Instertindex>=0&&Instertvalue<arr[Instertindex]){
arr[Instertindex+1]=arr[Instertindex];
Instertindex--;
// System.out.println(Instertindex);
}
arr[Instertindex+1]=Instertvalue;
};
System.out.println(Arrays.toString(arr));
}
}4.希尔排序
package 排序;
import java.util.Arrays;
public class 希尔排序
{
public static void main(String[] args) {
int[] arr = new int[]{3,5,2,7,8,1,2,0,4,7,4,3,8};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public 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;
}
}
}
}
}
}5.快速排序
package 排序;
import java.util.Arrays;
public class 快速排序 {
public static void main(String[] args) {
int[] arr = new int[]{4,7,6,7,8};
System.out.println(Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("改变后"+Arrays.toString(arr));
}
/**
*
* @param arr 排序数组
* @param start 开始位置
* @param end 结束位置
*/
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;
//处理所有小的数字
//System.out.println(low);
quickSort(arr,start,low);
//quickSort(arr,start,low);
//处理所有大的数字
quickSort(arr,low+1,end);
}
}
}6.归并排序
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。
概念：
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。**
过程展示：
package 排序;
import java.util.Arrays;
public class 归并排序 {
public static void main(String[] args) {
int[] arr = new int[]{1,3,5,2,4,6,8,10,9,7};
System.out.println(Arrays.toString(arr));
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
*
* @param arr
* @param start 开始下标
* @param end 结束下标
*/
public static void mergeSort(int[] arr, int start,int end) {
//分治结束条件
if (start>=end){
return;
}
//两位数的中位数
//通过位运算不会造成溢出
int mid = start+((end-start)>>1);
//处理左边
mergeSort(arr,start,mid);
//处理右边
mergeSort(arr,mid+1,end);
//归并
merge(arr,start,mid,end);
}
public static void merge(int[] arr,int start,int mid,int end){
//用于存储归并后的临时数组
int [] temp = new int[end-start+1];
//记录第一个数组中需要遍历的下标
int i = start;
//记录第二个数组中 需要遍历的下标
int j = mid+1;
//记录临时数组中存放的下标
int index = 0;
//遍历两个数组，取出小的数字放入临时数组中去
while (i<=mid&&j<=end){
if (arr[i]<=arr[j]){
//把小的数据放入临时数组中去
temp[index] = arr[i];
//临时数组下标加1
i++;
index++;
}else{
temp[index] = arr[j];
j++;
index++;
}
}
//处理多余的数据
while (j<=end){
temp[index] = arr[j];
j++;
index++;
}
while (i<=mid){
temp[index] = arr[i];
i++;
index++;
}
//把临时数组中的数据重新存入原数组
for (int k =0;k<temp.length;k++){
//不同数组的不同开始位置 左侧数组开始位置：0 右侧数组开始位置
arr[k+start] = temp[k];
}
}
}7.堆排序
package 排序;
import java.util.Arrays;
public class 堆排序 {
public static void main(String[] args) {
int[] arr = new int[]{9,6,8,7,0,1,10,4,2,4,5,7};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[]arr){
//开始位置是最后一个非叶子节点，即最后一个节点的父节点
int start = (arr.length-1)/2;
//预设为大顶堆
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);
}
}
/**
*
* @param arr
* @param size 调整次数
* @param index 子节点位置
*/
public 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);
}
}
}8.计数排序
排序思路
- 假设有N个数的数组Array，取值范围在（0~9）之间，所以初始化一个数组countArray大小为10（即最大值+1），然后全部初始化为0
- 遍历Array数组填充countArray数组。就是把Array数组的值作为countArray数组的下标然后+1
- 遍历countArray数组，把值按照顺序填回Array数组，最终输出结果即可
package 排序;
import java.util.Arrays;
public class 计数排序 {
public static void main(String[] args) {
int[] array = new int[]{0, 2, 4, 4, 1, 1, 6, 5, 8, 9, 9, 6};
int[] sortedArray = countSort(array);
System.out.println(Arrays.toString(sortedArray));
}
private static int[] countSort(int[] array) {
//求Array 数组的最大值
int max = 0;
for (int i = 0; i<array.length;i++){
if (array[i]>max){
max = array[i];
}
}
//创建一个长度为max +1 的数组
int [] countArray = new int[max+1];
//计数排序
for (int i = 0 ; i<array.length;i++){
countArray[array[i]]++;
}
int index = 0;
int[] sortedArray = new int [array.length];
for (int i = 0 ; i<countArray.length;i++){
for (int j=0;j<countArray[i];j++){
sortedArray[index++] = i;
}
}
return sortedArray;
}
}9.桶排序
import java.util.Arrays;
public class bucketSortTest {
public static void bucketSort(int[] num) {
// 遍历原始数组，找到数组中的最大值
int max = num[0];
for (int i = 0; i < num.length; i++) {
if (num[i] > max) {
max = num[i];
}
}
// 创建一个下标为原始数组中最大值的桶数组,该桶数组的下标代表元素，该数组下标所对应的值代表这个值出现的次数
int[] bucketArray = new int[max + 1];
// 再次遍历原始数组，得到原数组中存在的各个元素，以及出现的次数
for (int i = 0; i < num.length; i++) {
bucketArray[num[i]]++;
}
// 遍历桶数组,外层循环从桶的第一位开始（即下表为零）；内层循环遍历桶数组中下标为i的值出现的次数
int index = 0;
for (int i = 0; i < bucketArray.length; i++) {
for (int j = 0; j < bucketArray[i]; j++) {
num[index++] = i;
}
}
}
public static void main(String[] args) {
int[] num=new int[] { 2,5,6,8,5,2,9,6};
bucketSort(num);
System.out.println(Arrays.toString(num));
}
}10.基数排序
package 排序;
import java.util.Arrays;
public class 基数排序 {
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));
}
public 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];
}
}
System.out.println(max);
//计算最大数字是几位数
int maxlength = (max+"").length();
//用于临时存储数据的数组(最大长度为arr.lenth，一般情况下放不满)
int[][]temp = new int[10][arr.length];
//用于记录在相应的数组中存放的数字的数量
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++;
}
//把数量滞空
count[k]=0;
}
}
}
}
}
