最近在重新学习数据结构与算法,计划最近一年的业余时间都不干别的了,专门学算法。
今天给大家分享的是关于常见的几种排序算法:选择排序,冒泡排序和插入排序。这里的来代码源自于网传的左神算法新手班的内容,不过后面我整理了一份更加简洁的代码。
关于这几种排序算法,我之前是写过文章分析过的,不过这种经典的算法,就算学习100遍,练习10000遍也不过分,这里我重新梳理一下:
关于这几个算法,有几个核心需要注意:
选择排序:
for (i=0; i<数组长度-1; i++){
最小索引=i
for(j=i+1;j<数组长度;j++){
如果 arr[最小索引] > arr[j]{
最小索引=j
}
}
交换最小索引位置和i位置的元素的值
}
注意:外层循环只需要遍历到小于数组长度-1,因为内存循环是从i+1开始的,否则会索引越界,这里需要特别注意。
冒泡排序:
for (i=0; i<数组长度; i++){
for (j=0; j<数组长度-1-i; j++){
如果 arr[j] > arr[j+1]{
交换 j 和 j+1 索引位置的元素
}
}
}
注意:外层循环是小于数组长度,但是这里小于数组长度-1也是可以的。因为最后一次比较的时候,只剩下一个最小的数了,那次比较是可以被忽略掉的。
插入排序:
for (i=1; i<数组长度; i++){
for (j=i-1; j>=0 && arr[j]>arr[j+1]; j--){
交换j 和 j+1 索引位置的元素
}
}
注意:这里外层循环是从1开始的,因为内层循环要从i-1开始。内层循环j>=0表示左边有值,arr[j]>arr[j+1]表示左边的数大于右边的数。
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 选择排序,从左往右,每次选择最小的放左边,这样保证整个数组最后是从小到大的
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
// 从当前位置的后一个位置找到最后,找最小的那个数的索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 冒泡排序,从左往右,如果发现大的值,就往右移动(交换),这样保证后面的数都比前面的数大,所以是有序的
for (int i = 0; i < arr.length; i++) {
// 发现后一个数比前一个数大,就交换
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr,j,j+1);
}
}
}
}
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 插入排序,从左往右,每次保证左边的数组是有序的,最后整个数组都是有序的
// 因为这有点像大牌,习惯性的把小牌放左边,大牌放右边,所以形象的比喻为插入排序
for (int i = 1; i < arr.length; i++) {
// 保证左边是有序的,如果左边有值且左边的值比右边的大
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
package com.zhangdapeng520.z02_select_sort;
import java.util.Arrays;
/**
* @文件 Z01Hello.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述
* @创建时间 2022-10-18 07:53:00
* @更新时间 2022-10-18 07:53:00
*/
public class Z01Hello {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() [0,1)
// Math.random() * N [0,N)
// (int)(Math.random() * N) [0, N-1]
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
// [-? , +?]
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
selectionSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
selectionSort(arr);
printArray(arr);
}
}
package com.zhangdapeng520.z02_select_sort;
import java.util.Arrays;
/**
* @文件 Practice01.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述
* @创建时间 2022-10-18 08:11:00
* @更新时间 2022-10-18 08:11:00
*/
public class Practice01 {
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 选择排序,从左往右,每次选择最小的放左边,这样保证整个数组最后是从小到大的
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
// 从当前位置的后一个位置找到最后,找最小的那个数的索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[] getArr(int size){
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i]=(int)(Math.random()*100);
}
return arr;
}
public static void main(String[] args) {
int[] arr = getArr(10);
System.out.println(Arrays.toString(arr));
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
}
package com.zhangdapeng520.z03_bubble_sort;
import java.util.Arrays;
/**
* @文件 Z01Hello.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述
* @创建时间 2022-10-18 07:54:00
* @更新时间 2022-10-18 07:54:00
*/
public class Z01Hello {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
// 交换arr的i和j位置上的值
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
bubbleSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
bubbleSort(arr);
printArray(arr);
}
}
package com.zhangdapeng520.z03_bubble_sort;
import java.util.Arrays;
/**
* @文件 Practice01.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述
* @创建时间 2022-10-18 08:11:00
* @更新时间 2022-10-18 08:11:00
*/
public class Practice01 {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 冒泡排序,从左往右,如果发现大的值,就往右移动(交换),这样保证后面的数都比前面的数大,所以是有序的
for (int i = 0; i < arr.length; i++) {
// 发现后一个数比前一个数大,就交换
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr,j,j+1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[] getArr(int size){
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i]=(int)(Math.random()*100);
}
return arr;
}
public static void main(String[] args) {
int[] arr = getArr(10);
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
package com.zhangdapeng520.z04_insert_sort;
import java.util.Arrays;
/**
* @文件 Z01Hello.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述
* @创建时间 2022-10-18 07:59:00
* @更新时间 2022-10-18 07:59:00
*/
public class Z01Hello {
// 从左到右,每次保证一小段数组是有序的,最终整个数组都是有序的
// 就像斗地主一样,我们习惯性的将小牌放左边,大牌放右边,形象的比做插入排序
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
// int j = i - 1; j >= 0 && arr[j] > arr[j + 1]
// 表示左边有数,并且左边的数比我大,就交换
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
// i和j,数交换
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() -> [0,1) 所有的小数,等概率返回一个
// Math.random() * N -> [0,N) 所有小数,等概率返回一个
// (int)(Math.random() * N) -> [0,N-1] 所有的整数,等概率返回一个
int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random())
- (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100; // 随机数组的长度0~100
int maxValue = 100;// 值:-100~100
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
insertionSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
// 打印arr1
// 打印arr2
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
insertionSort(arr);
printArray(arr);
}
}
package com.zhangdapeng520.z04_insert_sort;
import java.util.Arrays;
/**
* @文件 Practice01.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述
* @创建时间 2022-10-18 08:11:00
* @更新时间 2022-10-18 08:11:00
*/
public class Practice01 {
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 插入排序,从左往右,每次保证左边的数组是有序的,最后整个数组都是有序的
// 因为这有点像大牌,习惯性的把小牌放左边,大牌放右边,所以形象的比喻为插入排序
for (int i = 1; i < arr.length; i++) {
// 保证左边是有序的,如果左边有值且左边的值比右边的大
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[] getArr(int size) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = (int) (Math.random() * 100);
}
return arr;
}
public static void main(String[] args) {
int[] arr = getArr(10);
System.out.println(Arrays.toString(arr));
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
}