哪个网站能下载gif,photoshop下载手机版,wordpress 文章页插件,郑州企业网站建设我们都知道#xff0c;在应届面试的时候#xff0c;问到最多的就是快速排序#xff0c;快速排序是最经典、最常用的排序算法#xff0c;因为它的平均效率最优#xff0c;也最稳定。 快速排序使用了分治的算法思想#xff0c;分治算法本身理解起来很符合人类的思路#x…我们都知道在应届面试的时候问到最多的就是快速排序快速排序是最经典、最常用的排序算法因为它的平均效率最优也最稳定。 快速排序使用了分治的算法思想分治算法本身理解起来很符合人类的思路递归是很容易被理解的其最关键的一步就是划分了算法导论上介绍了一种划分方法和我在数据结构课上学的略有不同昨晚我把它们全都用java实现了。 这个是算法导论的版本 1 /**2 * 快速排序的划分方法一算法导论版本 sit的下一个比最后一个大3 * 4 * param begin5 * param end6 * return7 */8 private int QuickMergeA(int begin, int end) {9 System.out.print(初始 arr);
10 System.out.print(begin end);
11 int anchor (int) arr.get(end);
12 int sit begin - 1;
13 int temp;
14 for (int i begin; i end; i) {
15 if ((int) arr.get(i) anchor) {
16 sit;
17 temp (int) arr.get(i);
18 arr.set(i, (int) arr.get(sit));
19 arr.set(sit, temp);
20 }
21 }
22 temp (int) arr.get(sit 1);
23 arr.set(sit 1, anchor);
24 arr.set(end, temp);
25 System.out.print(arr);
26 System.out.println(sit 1);
27 return sit 1;
28 } 不难看出这个版本的划分思路是从数组一端往另一端推进对于比指定元素小的值均放在左侧比指定元素大的值放在右侧。 然后我们再看我数据结构课本上学过的版本 /*** 快速排序的划分方法二数据结构课本版本* * param begin* param end* return*/private int QuickMergeB(int begin, int end) {System.out.print(初始 arr);System.out.print(begin end);int anchor arr.get(end);int send end - 1;int temp;int tbegin begin;while (begin send) {while (arr.get(begin) anchor begin end - 1) {begin;}while (send tbegin arr.get(send) anchor) {send--;}if (begin send) {temp arr.get(begin);arr.set(begin, arr.get(send));arr.set(send, temp);}if (begin send) {temp arr.get(begin);arr.set(begin, arr.get(end));arr.set(end, temp);}}System.out.print(arr);System.out.println(send 1);return send 1;} 可以看出这种思路是两端推进的手段两端同时推进同样是左边存放比指定元素小的值右边存放比指定元素大的值。 这两种方法遍历数组的推进方法虽然不同但是其效率是一致的划分一次都相当于是要遍历一次子数组。其划分的包装入口也是相似的 /*** 快速排序入口* * param begin* param end*/private void QuickSequence(int begin, int end) {// if (begin end) {// int q QuickMergeA(begin, end);// this.QuickSequence(begin, q - 1);// this.QuickSequence(q 1, end);// }if (begin end) {int q QuickMergeB(begin, end);this.QuickSequence(begin, q - 1);this.QuickSequence(q 1, end);}} 需要指明的是测试上面方法的过程中应该把arr数组设置为静态的在java中实现类似于C的地址访问的情况我经常使用静态变量。 最古老的排序算法是插入排序之前学习数据结构的时候对于各种排序算法总是混淆比如对于快速排序和插入排序的算法思路都明白但是总是把快速排序当成插入排序插入排序当成快速排序。也许是当时两节课学了冒泡排序、快速排序、插入排序、堆排序等太多的排序算法吧加上编程经验少造成的。 其实插入排序很容易和快速排序区分开。因为插入排序是真的“插入”。插入排序的基础是左侧数据已经排序准确你要做的是把下一个数插入到有序数组的指定位置你可以脑补扑克牌。 /*** 插入排序*/private void InsertSequence() {for (int i 0; i arr.size(); i) {int p 0;while (p i arr.get(p) arr.get(i)) {p;}if (p i) {int temp arr.get(i);for (int k i; k p; k--) {arr.set(k, arr.get(k - 1));}arr.set(p, temp);}}} 插入排序的代码很短但是我们的经验是短的代码代表思路简单不代表效率高。其实是这样的插入排序的效率是N^2,而快速排序的效率则是NlogN。插入排序是最朴素的排序算法也是相对较慢的排序算法。 学数据结构的课程时我非常喜欢堆排序。或许是因为它是最形象的排序算法。其实堆排序利用特有的数据结构高效的做了这么一件事每次找出最小的数然后从数组中删掉这个数继续查找。 1 private void MaintainHeap(int length) {2 int temp;3 for (int i length / 2 - 1; i 0; i--) {4 if ((arr.get(i) arr.get((i 1) * 2 - 1))5 || ((i 1) * 2 length arr.get(i) arr6 .get((i 1) * 2))) {7 if ((i 1) * 2 length) {8 if (arr.get((i 1) * 2) arr.get((i 1) * 2 - 1)) {9 temp arr.get(i);
10 arr.set(i, arr.get((i 1) * 2 - 1));
11 arr.set((i 1) * 2 - 1, temp);
12 } else {
13 temp arr.get(i);
14 arr.set(i, arr.get((i 1) * 2));
15 arr.set((i 1) * 2, temp);
16 }
17
18 } else {
19 temp arr.get(i);
20 arr.set(i, arr.get((i 1) * 2 - 1));
21 arr.set((i 1) * 2 - 1, temp);
22 }
23
24 }
25 }
26
27 System.out.println(arr);
28 }
29
30 private void Heapsequence(int length) {
31 for (int i length; i 0; i--) {
32 this.MaintainHeap(i);
33 int temp arr.get(0);
34 arr.set(0,arr.get(i - 1));
35 arr.set(i - 1, temp);
36 }
37 } 堆排序的重要步骤是堆的维护。对于最大堆而言要确保特定个元素构建的堆中每个节点的值都大于其孩子节点这通常的方法是从最后一个有子节点的节点开始遍历到根节点对于这其间的每一个结点如果其子节点存在大于当前节点的节点则把最大的子节点同当前节点交换并同时维护交换后的子节点的状态这个子节点的子节点可能在交换后比子节点的值大。 除了上面的排序算法我们常见的还有冒泡排序之类。同时我在算法导论上还接触过计数排序、基数排序、桶排序等线性排序算法。因为其思路比较简单所以这里只给出一般思路 计数排序顾名思义使用了一个计数数组对于每一个值初始计数为0每新增一个该计数就增加一最后形成一个排序序列。计数排序的效率一般但是由于其稳定常常作为其它排序算法基本过程的算法使用。 基数排序是另外一种比较有意思的排序算法它先从最低位对数据进行排序然后再依次上升到最高位而对每个数位的排序他通常使用计数排序。 桶排序是效率最高的排序算法但是它对数据要求较高同时是一种以空间换时间的排序算法。它的方案是先new一个足够大的数组然后对待排序数组遍历将新数组键等于待排序数组中值的位置置为一多个则继续增一然后遍历新数组即可得到待排序数组的顺序。这种算法不适合离散性数据也不适合不知道范围的数据排序。 对于常规排序算法冒泡排序适合只有少数数据不在正确位置上的数据快速排序的平均效率最高堆排序性能极不稳定插入排序的效率较差。 以上。 转载于:https://www.cnblogs.com/toocooltohavefriends/p/5349375.html
