江苏龙网

  1. 主页 > 生活百科 > >

话不多说！程序员必学的十大算法( 三 )

程序员为什么一定要

4 // 如果 left == right，表示数组只有一个元素，则不用递归排序
5 if (left < right) {
6 // 把大的数组分隔成两个数组
7 int mid = (left + right) / 2;
8 // 对左半部分进行排序
9 arr = mergeSort(arr, left, mid);
10 // 对右半部分进行排序
11 arr = mergeSort(arr, mid + 1, right);
12 //进行合并
13 merge(arr, left, mid, right);
14 }
15 return arr;
16 }
17
18 // 合并函数，把两个有序的数组合并起来
19 // arr[left..mif]表示一个数组，arr[mid+1 .. right]表示一个数组
20 private static void merge(int[] arr, int left, int mid, int right) {
21 //先用一个临时数组把他们合并汇总起来
22 int[] a = new int[right - left + 1];
23 int i = left;
24 int j = mid + 1;
25 int k = 0;
26 while (i <= mid && j <= right) {
27 if (arr[i] < arr[j]) {
28 a[k++] = arr[i++];
29 } else {
30 a[k++] = arr[j++];
31 }
32 }
33 while(i <= mid) a[k++] = arr[i++];
34 while(j <= right) a[k++] = arr[j++];
35 // 把临时数组复制到原数组
36 for (i = 0; i < k; i++) {
37 arr[left++] = a[i];
38 }
39 }
40}
性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(n) 3、稳定排序 4、非原地排序
然而面试官要你写个非递归式的归并排序怎么办？别怕，我这还撸了个非递归式的归并排序，代码如下：
1public class MergeSort {
2 // 非递归式的归并排序
3 public static int[] mergeSort(int[] arr) {
4 int n = arr.length;
5 // 子数组的大小分别为1，2，4，8...
6 // 刚开始合并的数组大小是1，接着是2，接着4....
7 for (int i = 1; i < n; i += i) {
8 //进行数组进行划分
9 int left = 0;
10 int mid = left + i - 1;
11 int right = mid + i;
12 //进行合并，对数组大小为 i 的数组进行两两合并
13 while (right < n) {
14 // 合并函数和递归式的合并函数一样
15 merge(arr, left, mid, right);
16 left = right + 1;
17 mid = left + i - 1;
18 right = mid + i;
19 }
20 // 还有一些被遗漏的数组没合并，千万别忘了
21 // 因为不可能每个字数组的大小都刚好为 i
22 if (left < n && mid < n) {
23 merge(arr, left, mid, n - 1);
24 }
25 }
26 return arr;
27 }
28}
6、快速排序
我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的 。也就是说，我们无需再移动中轴元素的位置 。
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置 。
为方便理解我还准备了动图：

话不多说！程序员必学的十大算法

文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：不要在问我快速排序
代码如下：
1public class QuickSort {
2 public static int[] quickSort(int[] arr, int left, int right) {
3 if (left < right) {
4 //获取中轴元素所处的位置
5 int mid = partition(arr, left, right);
6 //进行分割
7 arr = quickSort(arr, left, mid - 1);
8 arr = quickSort(arr, mid + 1, right);
9 }
10 return arr;
11 }
12
13 private static int partition(int[] arr, int left, int right) {
14 //选取中轴元素
15 int pivot = arr[left];
16 int i = left + 1;
17 int j = right;
18 while (true) {
19 // 向右找到第一个小于等于 pivot 的元素位置
20 while (i <= j && arr[i] <= pivot) i++;
21 // 向左找到第一个大于等于 pivot 的元素位置
22 while(i <= j="">= pivot ) j--;
23 if(i >= j)
24 break;
25 //交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
26 int temp = arr[i];
27 arr[i] = arr[j];
28 arr[j] = temp;
29 }
30 arr[left] = arr[j];
31 // 使中轴元素处于有序的位置
32 arr[j] = pivot;
33 return j;
34 }
35}
性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(logn) 3、非稳定排序 4、原地排序
7、堆排序
堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值 。


推荐阅读


上一篇：yrs是什么意思？

下一篇：小雪节气的由来和传统民俗有哪些？