排序算法总结

排序算法

冒泡排序

N个数字进行冒泡排序，一共比较N-1轮，每轮比较N-1-i次，每次相邻的元素进行比较，满足条件进行交换

public static void main(String[] args) {// 冒泡排序int[] arr = { 9, 3, 6, 2, 1, 4, 5, 7 };// 外层循环控制轮数// 内存循环控制每轮比较的次数for (int i = 0, n = arr.length; i < n - 1; i++) {for (int k = 0; k < n - 1 - i; k++) {if (arr[k] > arr[k + 1]) {// 采用异或运算符交换相邻元素arr[k] = arr[k] ^ arr[k + 1];arr[k + 1] = arr[k] ^ arr[k + 1];arr[k] = arr[k] ^ arr[k + 1];isSort = false;}}}System.out.println(Arrays.toString(arr));}

上述代码即冒泡排序的体现，如果数组顺序已经有序，冒泡排序仍然会进行多轮比对，所以需要对冒泡排序进行优化

public static void main(String[] args) {// 冒泡排序的优化int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };// 外层循环控制轮数// 内存循环控制每轮比较的次数for (int i = 0, n = arr.length; i < n - 1; i++) {boolean isSort = true;for (int k = 0; k < n - 1 - i; k++) {if (arr[k] > arr[k + 1]) {// 采用异或运算符交换相邻元素arr[k] = arr[k] ^ arr[k + 1];arr[k + 1] = arr[k] ^ arr[k + 1];arr[k] = arr[k] ^ arr[k + 1];isSort = false;}}System.out.println(Arrays.toString(arr));// 优化冒泡排序，如果未发生交换（证明数组有序），直接跳出循环if (isSort) {break;}}System.out.println(Arrays.toString(arr));}

乱序算法

Fisher-Yates乱序算法

思想：每个元素都参与打乱，从数组的末尾元素向前打乱，每个元素和一个随机下表的元素进行交换

// 乱序排序public static void main(String[] args) {int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };for (int i = arr.length - 1; i > 0; i--) {// 产生随机下标int index = (int) (Math.random() * i);arr[i] = arr[i] ^ arr[index];arr[index] = arr[i] ^ arr[index];arr[i] = arr[i] ^ arr[index];}System.out.println(Arrays.toString(arr));}

查找算法

无序数组 —- 线性查找

// 无序数组的线性查找public static void main(String[] args) {int[] arr = {1,4,2,4,6,8,5,7,9};int target = 5;int index = -1;for(int i= 0 ; i<arr.length-1 ; i++) {if(arr[i] == target) {index = i;break;}}System.out.println(index);}

有序数组 —- 二分查找

思想：找到数组的中间值，如果目标值小于中间元素，则说明目标元素在中间元素的左边，即把最大下标变为mid-1；如果目标值大于中间元素，则说明目标元素在中间元素的游标，即把最小下标变为mid+1

// 有序序列二分查找public static void main(String[] args) {int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };int target = 3;int index = -1;int low = 0, high = arr.length - 1;while (low <= high) {int mid = (low + high) / 2;if (target == arr[mid]) {index = mid;break;} else if (target > arr[mid]) {low = mid + 1;} else if (target < arr[mid]){high = mid - 1;}}System.out.println(index);}

数组旋转

向左旋转

向左旋转：数组顺序遍历，将头部元素，不断交换至尾部
eg：将数组向左旋转一位

int[] numbers2 = {1,2,3,4,5,6,7};// 向左旋转：首位元素不断向后交换for(int k = 0 ; k<numbers2.length-1 ; k++) {numbers2[k] = numbers2[k]^numbers2[k+1];numbers2[k+1] = numbers2[k]^numbers2[k+1];numbers2[k] = numbers2[k]^numbers2[k+1];}System.out.println("向左旋转一位"+Arrays.toString(numbers2));

向右旋转

向右旋转：数组逆序遍历，将尾部元素，不断交换至头部

int[] numbers1 = {1,2,3,4,5,6,7};// 向右旋转：末尾元素不断向前交换for(int i = 0 ; i<3 ; i++) {for(int k = numbers1.length-1; k>0 ; k--) {numbers1[k] = numbers1[k]^numbers1[k-1];numbers1[k-1] = numbers1[k]^numbers1[k-1];numbers1[k] = numbers1[k]^numbers1[k-1];}}System.out.println("向右旋转三位"+Arrays.toString(numbers1));