1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 选择排序：
* 算法思想：
*
1、将数组的第一个数字设置为标志位最小数并记录最小数下标。
*
2、向后遍历，发现更小数后将该数与标志位互换位置并更新最小数与最小数下标。
*
3、循环完成排序
*/
public static void main(String[] args) {
int[] arr = new int[]{1, 6, 8, 9, 2, 3, 5, 4, 7};
for (int i = 0; i < arr.length - 1; i++) {//每次循环都会找出最小的数
int minIndex = i;//记录最小数的下标
int minNum = arr[i];//记录最小数
for (int j = i + 1; j < arr.length; j++) {//每次循环都会找出最小的数
if (arr[j] < minNum) {//如果当前数比最小数小，则更新最小数
minNum = arr[j];//更新最小数
minIndex = j;//更新最小数的下标
}
}
arr[minIndex] = arr[i];//将最小数放到最前面
arr[i] = minNum;//将标志位放到最小数原来所在的位置
}
System.out.println(Arrays.toString(arr));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 冒泡排序
*/
public static void main(String[] args) {
int[] arr = {6,2,3,7,1,4};
int len = arr.length;
//外层循环控制总体次数
for(int i = 1; i < len; i++) {
//如何实现每次冒泡？
//i==1
j: len-2
//i==2	j: len-3
for(int j = 0; j < len-i; j++) {
//比较j
j+1 两个位置上的值
//然后进行交换
if(arr[j] > arr[j+1]) {
arr[j] = arr[j] ^ arr[j+1];
arr[j+1] = arr[j] ^ arr[j+1];
arr[j] = arr[j] ^ arr[j+1];
}
}
System.out.println(Arrays.toString(arr));
}
System.out.println(Arrays.toString(arr));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 插入排序
*/
public static void main(String[] args) {
int[] a= {19,3,56,8,55,89,1};
//循环每一个数
for(int i=0;i<a.length;i++) {
//将a[i]向前移动,移动到前面一个值比他小或者是前面没有值就停下来
//因为是向前移动,所以j是--的
for(int j=i;j>0;j--) {
if(a[j]<a[j-1]) {
int tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}else {
//如果值和他相等或者是比他小的话,就可以不用再往前移动了
break;
}
}
System.out.println("第" + i + "次排序的结果是：" + Arrays.toString(a));
}
System.out.println("新数组为"+Arrays.toString(a));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
* 核心思想 —— 分组插入排序。
*
改变步长，用每种步长把数据划分成相应的分组；
*
然后对每个组内的数据进行排序。
*/
public static void main(String[] args) {
//需要进行排序的数组
int[] array = new int[]{8, 3, 2, 1, 7, 4, 6, 5};
//输出原数组的内容
System.out.print("原数组：");
printResult(array);
//shell排序操作
System.out.println("-------------------------------");
System.out.println("shell排序开始：");
shellSort(array);
System.out.println("shell排序结束：");
System.out.println("-------------------------------");
//输出排序后的相关结果
System.out.print("最后结果：");
printResult(array);
}
/**
* shell排序算法
* 增量h=(h*3)+1;
*/
private static void shellSort(int[] array) {
//首先根据数组的长度确定增量的最大值
int h = 1;
// 按h * 3 + 1得到增量序列的最大值
while (h <= array.length / 3) {
h = h * 3 + 1;
}
//进行增量查找和排序
while (h > 0) {
for (int i = h; i < array.length; i++) {
for (int k = i; k < array.length; k += h) {
//判断是否需要重新排序,如果小于k-h处的值，需要重新排序
if (array[k] < array[k - h]) {
int tempValue = array[k];
int j = k;
for (; j >= i && tempValue < array[j - h]; j -= h) {
array[j] = array[j - h];
}
array[j] = tempValue;
}
}
printResult(array);
}
h = (h - 1) / 3;
}
}
/**
* 输出相应数组的结果
*/
private static void printResult(int[] array) {
for (int value : array)
System.out.print(" " + value + " ");
System.out.println();
}
/**
* 交换数组中两个变量的值
*/
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
//归并排序
public int[] sortArray(int[] nums) {
//临时数组result
int[] result=new int[nums.length];
//归并排序
mergeSort(nums,0,nums.length-1,result);
//此时nums与result相同
return result;//此时nums与result相同
}
// 对 nums 的 [start, end] 区间归并排序
public void mergeSort(int[] nums,int start,int end,int[] result){
// 只剩下一个数字，停止拆分
if(start==end) return;
int middle=(start+end)/2;
// 拆分左边区域，并将归并排序的结果保存到 result 的 [start, middle] 区间
mergeSort(nums,start,middle,result);
// 拆分右边区域，并将归并排序的结果保存到 result 的 [middle + 1, end] 区间
mergeSort(nums,middle+1,end,result);
// 合并左右区域到 result 的 [start, end] 区间
merge(nums,start,end,result);
}
// 将 nums 的 [start, middle] 和 [middle + 1, end] 区间合并
public void merge(int[] nums,int start,int end,int[] result){
//分割
int middle=(start+end)/2;
// 数组 1 的首尾位置
int start1=start;
int end1=middle;
// 数组 2 的首尾位置
int start2=middle+1;
int end2=end;
// 用来遍历数组的指针
int index1=start1;
int index2=start2;
// 结果数组的指针
int resultIndex=start1;
//比较插入结果数组
while(index1<=end1 && index2<=end2){
if(nums[index1]<=nums[index2]){
result[resultIndex++]=nums[index1++];
}else{
result[resultIndex++]=nums[index2++];
}
}
// 将剩余数字补到结果数组之后
while(index1<=end1){
result[resultIndex++]=nums[index1++];
}
while(index2<=end2){
result[resultIndex++]=nums[index2++];
}
// 将 result 操作区间的数字拷贝到 arr 数组中，以便下次比较
for(int i=start;i<=end;i++){
nums[i]=result[i];
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
思路如下：
选定一个基准值pivot（通常指定为数组第一个值），比基准值大的放在右侧，比基准值小的放在左侧
*
指定左右两个指针分别为left，right ；left < right
*
指定函数退出条件，即left > right
*
先从右向左遍历，即右指针向左移动——right–操作，发现比pivot小的值暂停移动
*
再从左向右遍历，即左指针向右移动——left++操作，发现比pivot大的值暂停移动
*
交换左右指针发现的两个值的位置
*
当两指针相遇，即left == right，当前值与pivot交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 /**
* 快速排序：
* 思路如下：
*
选定一个基准值pivot（通常指定为数组第一个值），比基准值大的放在右侧，比基准值小的放在左侧
*
指定左右两个指针分别为left，right ；left < right
*
指定函数退出条件，即left > right
*
先从右向左遍历，即右指针向左移动——right–操作，发现比pivot小的值暂停移动
*
再从左向右遍历，即左指针向右移动——left++操作，发现比pivot大的值暂停移动
*
交换左右指针发现的两个值的位置
*
当两指针相遇，即left == right，当前值与pivot交换位置
*/
public static void main(String[] args) {
int[] arr = {-9, 78, 0, 0, 1, 0, 3, -1, 23, -56, 7};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] array, int low, int high) {
// 方法退出条件,指针相遇或错过
if (low >= high) {
return;
}
// 1. 指定基准值和左右指针记录位置
int pivot = array[low];
int l = low;
int r = high;
int temp = 0;
// 2. 遍历条件，左右指针位置
while (l < r) {
// 2.1 右侧遍历
while (l < r && array[r] >= pivot) {
r--;
}
// 2.2 左侧遍历
while (l < r && array[l] <= pivot) {
l++;
}
// 2.3 l指针还在r指针右侧，尚未相遇
if (l < r) {
temp = array[l];
array[l] = array[r];
array[r] = temp;
}
}
// 3. 当左右指针相遇，交换基准值位置
array[low] = array[l];
array[l] = pivot;
// 4. 根据条件左侧递归遍历
if (low < l) {
quickSort(array, low, l - 1);
}
// 5. 根据条件右侧递归遍历
if (r < high) {
quickSort(array, r + 1, high);
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] array = {4,6,1,2,9,8,3,5};
heapSort(array);
System.out.println(Arrays.toString(array));
}
/**
* 堆排序
*/
public static void heapSort(int[] arr){
//为什么从arr.length/2-1开始？
for (int i = arr.length/2-1; i >= 0 ; i--) {
adjustHeap(arr,i,arr.length);
}
for (int j = arr.length-1; j > 0; j--) {
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
/*为什么从0开始？
因为在第一次构建大顶堆后让堆顶元素和末尾元素进行交换
而对于其他的非叶子结点所对应的子树都是大顶堆就无需调整，
只需要堆顶元素(下标为0的非叶子结点)的子树调整成大顶堆
*/
adjustHeap(arr,0,j);
}
}
/**
* 构建大顶堆
* 注意：
*
这个方法并不是将整个树调整成大顶堆
*
而是以i对应的非叶子结点的子树调整成大顶堆
* @param arr 待调整的数组
* @param i 非叶子结点在数组中的索引(下标)
* @param length 进行调整的元素的个数，length是在逐渐减少的
*/
public static void adjustHeap (int[] arr,int i,int length){
/*取出当前非叶子结点的值保到临时变量中*/
int temp = arr[i];
/*j=i*2+1表示的是i结点的左子结点*/
for (int j = i * 2 + 1; j < length ; j = j * 2 + 1) {
if (j+1 < length && arr[j] < arr[j+1]){ //左子结点小于右子结点
j++; //j指向右子结点
}
if (arr[j] > temp){ //子节点大于父节点
arr[i] = arr[j]; //把较大的值赋值给父节点
//arr[j] = temp; 这里没必要换
i = j; //让i指向与其换位的子结点 因为
}else{
/*子树已经是大顶堆了*/
break;
}
}
arr[i] = temp;
}
}