排序算法 —— 插入排序、选择排序、冒泡排序、快速排序

欢迎指正。

最近打算重温一下排序算法。

插入排序

原理

插入排序主要是通过构建有序序列,对未排列的数据,从后往前扫描,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
public static void InsertSort(int[] array) {

for (int i = 1; i < array.length; i++) {
int j = i;
int target = array[i];
while (j > 0 && target < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = target;
}
}

选择排序

原理

第一次从下标为0的开始下标为0的这个数与后面的n-1个进行比较;找出最小或者最大的放在下标为0的这个位置。

时间复杂度是O(n^2)。不稳定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void SelectionSort(int[] array) {

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

for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int target = array[i];
array[i] = array[j];
array[j] = target;
}
}
}
}

冒泡排序

原理

  • 从第一个数据开始,与第二个数据相比较,如果第二个数据小于第一个数据,则交换两个数据的位置。
  • 指针由第一个数据移向第二个数据,第二个数据与第三个数据相比较,如果第三个数据小于第二个数据,则交换两个数据的位置。
  • 依此类推,完成第一轮排序。第一轮排序结束后,最大的元素被移到了最右面。
  • 依照上面的过程进行第二轮排序,将第二大的排在倒数第二的位置。
  • 重复上述过程,没排完一轮,比较次数就减少一次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void BubbleSort(int[] arr){
int i, j;
int n = arr.length;
int target;
for (i = 0; i < n - 1; i++) {

for (j = 0; j < n - 1 - i; j++) {
//左边比右边大
if (arr[j] > arr[j + 1]) {
target = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = target;
}
}
}
}

快速排序

原理

快排的原理:在需要排序的数据中选择一个中心值(key),通过一趟排序将需要排序的数组分为两部分,其中以key为中心,key右边比key大,key左边比key小,然后重复这过程。

代码

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
public static void quickSort(int a[]) {
sort(a, 0, a.length - 1);
}

public static void sort(int a[], int low, int hight) {
int i, j, target;
if (low > hight) {
return;
}
i = low;
j = hight;
target = a[i];
while (i < j) {
while (i < j && a[j] >= target) {
j--;
}
// 用比基准小的记录替换低位记录
if (i < j) {
a[i++] = a[j];
}
while (i < j && a[i] < target) {
i++;
}
// 用比基准大的记录替换高位记录
if (i < j) {
a[j--] = a[i];
}
}
// 将基准数值替换回 a[i]
a[i] = target;
// 对低子表进行递归排序
sort(a, low, i - 1);
// 对高子表进行递归排序
sort(a, i + 1, hight);
}
博主 wechat
钟意作者
客官,赏一杯coffee嘛~~~~
0%