logo头像

小玉的技术博客

排序算法

选择排序

一种最简单的排序算法是这样的: 首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置 (如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素位置交换 。如此往复, 直到将整个数组排序。这种方法叫做选择排序,因为它在不断地选择剩余元素之中的最小者。

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
public class selectSort {
/*
* 基本思路先找到数组中最小的元素,然后与数组的第一个元素交换,然后再找到剩下数组元素中的最小元素,与数组中的第二个元素位置交换
* */
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={4,8,2,47,56,3,9};
System.out.println("交换之前:");
for(int num:arr){
System.out.print(num+" ");
}
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i; //用k 来标记最小元素的下标
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("交换后:");
for(int num:arr){
System.out.print(num+" ");
}
}
}

冒泡排序算法

冒泡排序外层共需要对序列进行n-1次遍历,内层从e[0]到e[n-i](i为外层遍历的次数)两两进行比较,如果e[j-1]>e[j]则进行交换,直到比较e[0]和e[1]后为止,冒泡排序算法的时间复杂度为O(n²);

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
public class bubleSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
/*
* 基本思路:两个元素进行比较,
*/
int[] arr = {4,3,2,6,7,1,8,5};
System.out.print("冒泡排序之前:");
for (int i : arr) {
System.out.print(i + " ");
}
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
if (arr[j]<arr[i]) {
int k = arr[i];
arr[i] = arr[j];
arr[j] = k;
}
}
}
System.out.print("冒泡排序之后:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}

支付宝打赏 微信打赏

赞赏是不耍流氓的鼓励