冒泡排序
冒泡排序的核心思想是两两进行对比交换。从索引 i=0 开始，索引 i 所对应的值与索引 i+1 所对应的值进行对比交换。不断进行以上操作，每一轮都会让至少一个数变得符合顺序。
package com.test;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {2,1,6,5,8,7,4,3};
sort(arr);
}
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}简单选择排序
将待排序数组中的最小值与第一个数进行交换。我们需要定义一个游标，其永远指向待排序数组中的第一个数。
package com.test;
import java.util.Arrays;
public class SearchSort {
public static void main(String[] args) {
int[] arr = {2,1,6,5,8,7,4,3};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = arr[i];
int MinIndex = i;
for (int j = i; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
MinIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[MinIndex];
arr[MinIndex] = temp;
}
}
}基数排序
个位、十位、百位…依次变得有序。
首先定义0~9共十个桶。
首先按个位排序。
然后将数据依次取出。
然后按十位排序。
然后将数据依次取出。
然后按百位排序……
如何实现基数排序
1、桶从哪来
十个桶可以用一个二维数组来代替。
考虑到极端情况（十个数取值相同），桶的高度一定是数组的长度。
我们以个位为例：
for (int i = 0; i < arr.length; i++) {
int element = arr[i] % 10;
}element的作用是确定将数据储存到哪个桶当中。
为了明确往桶的哪个位置放入数值，我们定义一个桶记录器。桶记录器记录当前桶中有几个数据。
2、如何将数据取出
如果桶记录器对应的值不为0，则将桶中的数据依次取出。
以下是将个位排序的代码
package com.test;
import java.util.Arrays;
public class JiShuSort {
public static void main(String[] args) {
int[] arr = {88,4,2,10,9,8,14,201,874,12,63,78,94,26,62,41,19};
sort(arr);
}
public static void sort(int[] arr) {
//创建桶
int[][] bucket = new int[10][arr.length];
//创建桶记录器
int[] bucketCount = new int[10];
//排序个位
for (int i = 0; i < arr.length; i++) {
int element = arr[i] % 10;
int count = bucketCount[element];
bucket[element][count] = arr[i];
bucketCount[element]++;
}
int i = 0;
//数据取出
for (int k = 0; k < bucketCount.length; k++ ) {
if (bucketCount[k] != 0) {
for (int h = 0; h < bucketCount[k]; h++) {
arr[i] = bucket[k][h];
i++;
}
}
}
System.out.println(Arrays.toString(arr));
}
}以下是完整的基数排序代码
package com.test;
import java.util.Arrays;
public class JiShuSort {
public static void main(String[] args) {
int[] arr = {88,4,2,10,9,8,14,201,874,12,63,78,94,26,62,41,19};
sort(arr);
}
public static void sort(int[] arr) {
//找到最大值
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
//确定最大值的位数
int MaxLength = (max + "").length();
//创建桶
int[][] bucket = new int[10][arr.length];
//创建桶记录器
int[] bucketCount = new int[10];
int n = 1;
for (int w = 0; w < MaxLength; w++) {
//排序
for (int i = 0; i < arr.length; i++) {
int element = arr[i] / n % 10;
int count = bucketCount[element];
bucket[element][count] = arr[i];
bucketCount[element]++;
}
int a = 0;
//数据取出
for (int k = 0; k < bucketCount.length; k++ ) {
if (bucketCount[k] != 0) {
for (int h = 0; h < bucketCount[k]; h++) {
arr[a] = bucket[k][h];
a++;
}
}
//清空桶记录器
bucketCount[k] = 0;
}
n *= 10;
}
System.out.println(Arrays.toString(arr));
}
}
插入排序
类似于冒泡排序，从索引为 i=1 的数据开始遍历，每次将前 i+1 个数排序。
package com.test;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {2,3,8,4,6,9,7,1,5,0};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i-1; j >= 0; j--) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}希尔排序
插入排序存在的问题：
当较小数据在后边，效率会受到较大影响。为了解决这个问题，我们使用希尔排序。
对希尔排序的介绍：使用了分组的思想，将数据两两分成一组，间隔是数组长度的一半。
然后在组内进行排序。
然后将数据再次分组，间隔是数组长度的四分之一。
然后在组内进行排序。
重复上述操作，直到间隔为1。
针对该情况，我们有以下代码
package com.test;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int arr[] = {5,7,4,2,0,3,1,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int i = 4; i < arr.length; i++) {
for (int j = i-4; j >= 0; j -= 4) {
if (arr[j] > arr[j+4]) {
int temp = arr[j];
arr[j] = arr[j+4];
arr[j+4] = temp;
}
}
}
for(int i = 2; i < arr.length; i++) {
for (int j = i-2; j >= 0; j -= 2) {
if (arr[j] > arr[j+2]) {
int temp = arr[j];
arr[j] = arr[j+2];
arr[j+2] = temp;
}
}
}
for(int i = 1; i < arr.length; i++) {
for (int j = i-1; j >= 0; j -= 1) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}以下是完整的希尔排序代码
package com.text;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for (int g = arr.length/2; g >= 1; g /= 2) {
for (int i = g; i < arr.length; i++) {
for (int j = i-g; j >= 0; j -= g) {
if (arr[j] > arr[j+g]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
}