비교정렬과 퀵정렬에 대한 자세한 설명

　퀵 정렬(Quick Sort)은 효율성이 높기 때문에(평균 O(nlogn)) 필기 시험 문제에서 자주 테스트됩니다.

빠른 정렬의 첫 번째 단계는 다른 숫자와 비교하고 교환하는 데 사용될 "기준"을 선택하는 것입니다. 이 "베이스"의 선택은 퀵 정렬의 효율성에 영향을 주지만, 베이스 선택을 위해 베이스를 선택하면 말보다 카트가 먼저 놓이게 됩니다. 예를 들어, 최적의 염기를 찾기 위해서는 정렬할 전체 시퀀스에서 중앙값을 찾아야 하는데, 중앙값을 찾는 것은 실제로 매우 비용이 많이 듭니다. 기본 선택은 일반적으로 정렬할 순서의 첫 번째 개체, 중간 개체 또는 마지막 개체입니다. 이 기사에서는 첫 번째 요소 선택을 예로 들어 빠른 정렬을 간략하게 분석하고 구현합니다.

{6, 5, 3, 1, 7, 2, 4}로 정렬할 열을 예로 들어 첫 번째 요소 6을 기본으로 선택합니다.

베이스를 선택한 후 배열 요소를 비교하고 교환해야합니다. 비교 방법과 대상은 무엇입니까? 빠른 정렬의 두 번째 단계는 배열의 첫 번째 요소와 마지막 요소에 "센티넬"을 설정하는 것입니다.

베이스를 선택하고 센티넬을 설정한 후 다음 단계는 비교를 시작하는 것입니다. 베이스를 마지막 센티넬 j보다 먼저 비교하고 센티넬 j와 교환합니다. 동시에 센디넬 i+1 .

이때, 베이스는 더 이상 센티넬 j와 비교되지 않고 센티넬 i와 비교됩니다. 베이스가 센티넬 i보다 클 경우 센티넬은 베이스보다 커질 때까지 뒤로 이동하고 센티넬 j-1 동시에 교환됩니다.

　 위의 단계를 반복하여 센티넬j와 베이스를 비교해 보세요.

최종 결과는 센티넬 i의 위치 = 센티널 j의 위치임을 보여줍니다. 이때 기본 값은 이 위치에 할당됩니다.

이런 식으로 6진수의 왼쪽 숫자는 모두 그보다 작고, 오른쪽 숫자는 모두 그보다 큽니다. 그런 다음 재귀를 사용하여 왼쪽과 오른쪽에서 동일한 단계를 수행합니다. 배열을 선택하여 기지를 선택하고 센트리를 설정한 후 마지막으로 정렬을 완료합니다.

　　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)

위 내용은 비교정렬과 퀵정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!