w88优德_w88体育_w88优德官网

首页w88正文

戒指尺寸,算法(一)-- 排序上-w88优德

admin4个月前345浏览量

算法里边最基本的便是排序了,这儿把几种常用排序算法总结一下。

写在前面

下面的排序都是按从小到大的排序来的。排序中都会涉及到交流元素,交流元素的办法许多,这儿供给一种位运算的交流办法:这儿一定要判别交流的方位是否共同,假如不判别的话会把当时方方位为0的。

public static void swap(int[] arr, int i, int j) {
//这儿一定要判别交流的方位是否共同,假如不判别的话会把当时方方位为0的
if (i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}

冒泡

public void bubbleSort(int[] arr) {
//假如数组为null 或许数据只需一个长度,直接回来
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}

冒泡排序的基本思想便是从把大的数像水里的气泡相同往上冒,也便是从一个数开端和后边的数就行比较,假如大于就交流,不然不进行交流,如此循环,直到最终一个数就会变成最大的数。再进行循环,把第二大的数放在倒数第二的方位上,最终就完成了排序。

时刻杂乱为O(N**2),空间杂乱度为O(1)

外层第一次for循环

上图中便是外层for循环一次的成果,初学算法的时分最不简单弄清楚的便是鸿沟值了。比方外层循环从什么值开端,内层循环从什么值开端。冒泡排序由于咱们把大数放后边,完毕的鸿沟值是在减小,所以外层循环从length-1开端。

挑选

public static void selectSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

for (int i = 0; i < arr.length - 1; i++) {

int minPosition = i;

for (int j = i + 1; j < arr.length; j++) {

minPosition = arr[j] < arr[minPosition] ? j : minPosition;

}

if (i != minPosition) {

swap(arr, i, minPosition);

}

}

}

冒泡排序的基本思想便是从把小的数放在最前面,不必每次都交流,仅仅符号最小数地点的方位,最终才进行交流,而冒泡排序只需契合条件都要交流。

时刻杂乱为O(N**2),空间杂乱度为O(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);
}
}
}

刺进排序的基本思想记住打扑克就行了,从第一张开端,每来一张新牌就顺次进行比较,假如比前面的小就交流,不然就中止。

时刻杂乱为O(N**2),空间杂乱度为O(1)

public static void bucketSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

//找出最大的数

int max = Integer.MIN_VALUE;

for (int i = 0; i < arr.length; i++) {

max = Math.max(max, arr[i]);

}

//创立最大的数+1巨细的数组

int[] bucket = new int[max + 1];

//遍历原数组,把值放到对应的桶中,放一次值+1

for (int i = 0; i < arr.length; i++) {

bucket[arr[i]]++;

}

//遍历一切的桶,假如桶里边的数是多少就输出几回

int i = 0;

for (int j = 0; j < bucket.length; j++) {

while (bucket[j]-- > 0) {

arr[i++] = j;

}

}

}

桶排序便是需求树立最大的数加1大的数组,然后把一切的数顺次放在对应的桶中,这也是一个不需求比较的排序算法。

时刻杂乱为O(N),空间杂乱度为O(N)

剩余的还有快速排序、堆排序和归并排序,下次再给我们共享。

期望对我们有所协助,有协助记得点赞哦!能够重视下,后边继续共享编程类的文章,谢谢!