Detailed explanation of comparison sorting and quick sorting

Quick sort (quick sort for short) is often tested in written examination questions because of its high efficiency (average O(nlogn)).

The first step for quick sorting is to select a "base", which will be used to compare and exchange with other numbers. The choice of this "base" will affect the efficiency of quick sorting, but if you choose the base for the sake of choosing the base, it will put the cart before the horse. For example, in order to find the optimal base, you need to find the median in the entire to-be-sorted sequence, but finding the median is actually very expensive. The choice of base is usually the first object, the middle object, or the last object in the sequence to be sorted. This article takes the selection of the first element as an example to make a brief analysis and implementation of quick sorting.

Taking the column to be sorted {6, 5, 3, 1, 7, 2, 4} as an example, select the first element 6 as the base.

After selecting the base, you need to compare and exchange with the array elements. How to compare and who to compare with? The second step of quick sort is to set a "sentinel" on the first element and the last element of the array.

After selecting the base and setting the sentinels, the next step is to start comparing. Compare the base with the last sentinel first j is compared, and if it is greater than sentinel j, it is exchanged with sentinel i+1.

At this time, the base is no longer compared with sentinel j, but with sentinel i. If the base is greater than sentinel i, the sentinel moves backward until it is greater than the base. So far, sentinel j-1 is exchanged at the same time.

Repeat the above steps and compare the base with sentinel j.

The final result shows that the position of sentinel i = the position of sentinel j. At this time, the base value is assigned to this position.

In this way, the numbers on the left side of base 6 are all smaller than it, and the numbers on the right side are all greater than it. Then use recursion to perform the same steps on the left and right arrays to select the base and set Sentinel, the sorting can be completed at the end.

　Java

 1 package com.algorithm.sort.quick; 2  3 import java.util.Arrays; 4  5 /** 6  * 快速排序 7  * Created by yulinfeng on 2017/6/26. 8  */ 9 public class Quick {10     public static void main(String[] args) {11         int[] nums = {6, 5, 3, 1, 7, 2, 4};12         nums = quickSort(nums, 0, nums.length - 1);13         System.out.println(Arrays.toString(nums));14     }15     16     /**17      * 快速排序18      * @param nums 待排序数组序列19      * @param left 数组第一个元素索引20      * @param right 数组最后一个元素索引21      * @return 排好序的数组序列22      */23     private static int[] quickSort(int[] nums, int left, int right) {24         if (left < right) {25             int temp = nums[left];    //基数26             int i = left;    //哨兵i27             int j = right;    //哨兵j28             while (i < j) {29                 while (i < j && nums[j] >= temp) {30                     j--;31                 }32                 if (i < j) {33                     nums[i] = nums[j];34                     i++;35                 }36                 while (i < j && nums[i] < temp) {37                     i++;38                 }39                 while (i < j) {40                     nums[j] = nums[i];41                     j--;42                 }43             }44             nums[i] = temp;45             quickSort(nums, left, i - 1);46             quickSort(nums, i + 1, right);47         }48         return nums;49     }50 }

　Python3

 1 #快速排序 2 def quick_sort(nums, left, right): 3     if left < right: 4         temp = nums[left]    #基数 5         i = left    #哨兵i 6         j = right    #哨兵j 7         while i < j: 8             while i < j and nums[j] >= temp: 9                 j -= 110             if i < j:11                 nums[i] = nums[j]12                 i += 113             while i < j and nums[i] < temp:14                 i += 115             if i < j:16                 nums[j] = nums[i]17                 j -= 118         nums[i] = temp19         quick_sort(nums, left, i - 1)20         quick_sort(nums, i + 1, right)21     22     return nums23 24 nums = [6, 5, 3, 1, 7, 2, 4]25 nums = quick_sort(nums, 0, len(nums) - 1)26 print(nums)

The above is the detailed content of Detailed explanation of comparison sorting and quick sorting. For more information, please follow other related articles on the PHP Chinese website!