本文最后更新于 780 天前，其中的信息可能已经有所发展或是发生改变，请谨慎参考。
冒泡排序
代码：
package com.xiheya.sort;
/**
* @Author {xiheya}
* @Date: 2022/03/16/ 17:21
* @Description
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1,3,2,6,5,9,4};
bubbleSort(arr);
System.out.print("finish: [" );
for (int x : arr) {
System.out.print(x + "\t");
}
System.out.println("]");
}
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;
}
}
}
}
}运行结果
冒泡排序的优化
代码
package com.xiheya.sort;
/**
* @Author {xiheya}
* @Date: 2022/03/16/ 17:21
* @Description
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1,3,2,6,5,9,4};
bubbleSort(arr);
System.out.print("finish: [" );
for (int x : arr) {
System.out.print(x + "\t");
}
System.out.println("]");
}
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) { //确定冒泡次数
//如果在某一次冒泡排序过程中，没有交换元素，则说明该数组已经有序。
//冒泡步骤
boolean flag = true;
for (int j = 0; j < arr.length - 1 -i; j++){
if (arr[j] > arr[j+1])
{
flag = false;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if (flag){
break;
}
}
}
}运行结果
选择排序
代码
package com.xiheya.sort;
/**
* @Author {xiheya}
* @Date: 2022/03/16/ 17:40
* @Description
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {1,3,-2,4,5};
selectSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) { //开始选择排序
//初始 min = arr[i]; mindex = i;
int min = arr[i];
int mindex = i;
for (int j = i + 1; j < arr.length - 1 ; j++){
//将min与其后面的数比较，如果min大于他后面的数 就更新min，及其下标
if (min > arr[j]){
min = arr[j];
mindex = j;
}
}
//如果 最小值的下标不等于 i 则交换 这两个元素的值
if (mindex != i){
arr[mindex] = arr[i];
arr[i] = min;
}
}
}
}运行结果
插入排序
代码
package com.xiheya.sort;
/**
* @Author {xiheya}
* @Date: 2022/03/16/ 18:08
* @Description
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = {1,3,2,5,4,-1};
insertSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//初始化insertdex 和 insertvalue
int insertdex = i;
int insertvalue = arr[i];
while (insertdex > 0 && insertvalue < arr[insertdex - 1]){ //while循环，当insertdex > 0 以及 insertvalue 小于 其前一个值时进入循环
// 将 前一个值 赋值给 下标为 insertdex的数组空间内
arr[insertdex] = arr[insertdex - 1];
// 下标往前移一位
insertdex--;
}
//当下标等于0 或者前面的数据均没有比insertvalue小时 结束循环，将insertvalue的值赋给 arr[insertdex]
arr[insertdex] = insertvalue;
}
}
}运行结果
快速排序
代码
package com.xiheya.sort;
/**
* @Author {xiheya}
* @Date: 2022/03/16/ 19:34
* @Description
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr ={1,3,-2,4,5,6};
quickSort(arr,0,arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void quickSort(int[] arr,int left, int right){
//递归退出条件
if (left >= right){
return;
}
//左指针与右指针
int l = left;
int r = right;
while (l < r){
while (l < r && arr[r] >= arr[left])r--; //右边的元素与arr[left]比较，直到出现一个比arr[left]小的数，r指针停止左移
while (l < r && arr[l] <= arr[left])l++; //左边的元素与arr[left]比较，直到出现一个比arr[left]大的数，l指针停止右移
if (l == r){ //当两个指针相遇时交换 arr[l]（arr[r]） 与 arr[left]的数据
int temp = arr[l];
arr[l] = arr[left];
arr[left] = temp;
}else{ //两个指针不相等时则交换 两指针内的数据
int temp = arr[r];
arr[r] = arr[l];
arr[l] = temp;
}
}
quickSort(arr,left,l-1); //通过递归，将左边的元素进行快排
quickSort(arr,r+1,right); //通过递归，将右边的元素进行快排。
}
}
运行结果
归并排序
代码
package com.xiheya.sort;
import java.util.Arrays;
/**
* @Author {xiheya}
* @Date: 2022/03/16/ 23:53
* @Description
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {1,3,2,6,4,9,7};
int[] temp = new int[arr.length];
mergeSort(arr,0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int left, int right, int[] temp){
if (left < right){
int mid = (left + right) / 2;
//分
mergeSort(arr,0,mid,temp); //将左边部分继续分
mergeSort(arr,mid+1,right,temp); //将右边部分继续分
//合
merge(arr,left,mid,right,temp);
}
}
//合
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid+1;
int t = 0; //临时数组下标索引
//先将两部分合并
while (i <= mid && j <= right){
if (arr[i] <= arr[j]){
temp[t] = arr[i];
i++;t++;
}else {
temp[t] = arr[j];
j++;t++;
}
}
//如果左边没有合并完全，则接着i继续合并
while (i <= mid){
temp[t] = arr[i];
t++;i++;
}
//如果右边没有合并完全，则接着j继续合并
while (j <= right){
temp[t] = arr[j];
t++;j++;
}
//接着将temp中的数组填充到指定位置
t = 0;
int templeft = left;
while (templeft <= right){
arr[templeft] = temp[t];
t++;templeft++;
}
}
}运行结果
基数排序
代码
package com.xiheya.sort;
import java.util.Arrays;
/**
* @Author {xiheya}
* @Date: 2022/03/17/ 0:45
* @Description
*/
public class RedixSort {
public static void main(String[] args) {
int[] arr = {10023,3225,302,155,9,3326,33,5987,663,15596};
redixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr){
int[][] bucket = new int[10][arr.length - 1]; //桶里面所存的具体数值
int[] bucketElementCounts = new int[10]; //每个桶所存的元素个数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(max < arr[i]) max = arr[i];
}
int maxCount = (max + "").length(); //获取最大数的位数
for (int i = 0; i < maxCount; i++) {
//把数组中的数都放在桶里面
for (int k = 0; k < arr.length; k++) {
int value = arr[k] / (int) Math.pow(10, i) % 10;
bucket[value][bucketElementCounts[value]] = arr[k];
bucketElementCounts[value]++;
}
int index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if(bucketElementCounts[k] != 0){
for (int x = 0; x < bucketElementCounts[k]; x++) {
arr[index] = bucket[k][x];
index++;
}
}
bucketElementCounts[k] = 0;
}
}
}
}运行结果
