In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-26 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >
Share
Shulou(Shulou.com)06/03 Report--
This article mainly explains "how to realize and optimize the fast sorting algorithm". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "how to implement and optimize the quick sorting algorithm"!
Preface
Quick sorting can be said to be the most widely used sorting algorithm, the main feature is based on in-situ sorting (no need to use auxiliary arrays, saving space); in fact, for the length of N array using fast sorting time complexity of NlogN; in the previous articles also discussed other sorting algorithms, have not been able to combine these two characteristics.
Quick sorting idea
Quick sorting is also a sort algorithm of divide-and-conquer, which divides the array into two sub-arrays, and then sorts the sub-arrays recursively to ensure the order of the whole array.
The idea of the algorithm:
Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community
Randomly select a syncopated element, usually the first element of the array
Scan from the left side of the array to find values greater than or equal to split elements, scan from the right side of the array to find values less than or equal to split elements, and exchange these two values
Loop this process until the left and right pointers meet, so that an element is arranged, ensuring that the value on the left side of the slicing element is less than its value, and the element on the right is greater than its value.
Recursion is a process that ultimately ensures that the whole array is in order.
Algorithm realization
According to the idea of the quick sort algorithm, we can write the first version of the implementation:
Public class QuickSort implements SortTemplate {@ Override public void sort (Comparable [] array) {quickSort (array, 0, array.length-1);} private void quickSort (Comparable [] array, int lo, int hi) {if (lo > = hi) {return;} int partition = partition (array, lo, hi); quickSort (array, lo, partition-1) QuickSort (array, partition + 1, hi);} private int partition (Comparable [] array, int lo, int hi) {int I = lo, j = hi + 1; Comparable el = array [lo]; while (true) {while (less (Array [+ + I], el)) {if (I = hi) {break }} while (less (el, array [--j])) {if (j = = lo) {break;}} if (I > = j) {break } exch (array, I, j);} exch (array, lo, j); return j;}}
This code is a regular implementation of quick sorting. In the worst case, if the array that needs to be sorted is already ordered, the process of performing quick sorting is shown in figure:
For an array of length N, in the worst case, it needs recursive Nmuri once, so the time complexity is O (N2). In order to avoid this, let's take a look at how to improve the algorithm.
Algorithm improvement
To avoid the worst-case scenario, there are two ways to ensure randomness. the first is to randomly scramble the array before sorting the array, and the second is to randomly take the slicing element in the partition method instead of taking the first one to simply implement:
Private int partition (Comparable [] array, int lo, int hi) {int I = lo, j = hi + 1; int random = new Random (). NextInt (hi-lo) + lo; exch (array, lo, random); Comparable el = array [lo]; while (true) {while (less (Array [+ + I], el)) {if (I = = hi) {break }} while (less (el, array [--j])) {if (j = = lo) {break;}} if (I > = j) {break;} exch (array, I, j);} exch (array, lo, j); return j }
Switch to insert sort, just like merge sort, switch to insert sort directly for decimal array.
Private void quickSort (Comparable [] array, int lo, int hi) {if (lo > = hi) {return;} if (hi-lo)
< 5) { //测试,小于5就切换到插入排序 insertionSort(array, lo, hi); return; } int partition = partition(array, lo, hi); quickSort(array, lo, partition - 1); quickSort(array, partition + 1, hi); } //插入排序 private void insertionSort(Comparable[] array, int lo, int hi) { for (int i = lo; i lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } } } 三向切分 当我们需要排序的数组中出现了大量的重复元素,我们实现的快速排序在递归的时候会遇到许多全部重复的子数组,我们的算法依然会对其进行切分,这里有很大的提升空间。 思路就是先随意选择一个切分元素(el),然后把数组切换成大于、等于、小于三个部分,一次递归可以排定所有等于切分元素的值;维护一个指针lt、gt,使得a[lo..lt-1]都小于切分元素,a[gt+1..hi]都大于切分元素; 初始化变量:lt=lo, i=lo+1, gt=hi if a[i] < el ; 交换a[i]与a[lt], i++, lt++ if a[i] >El; exchange a [GT] with a [I], gt--
A [I] = = el; iTunes +
Code implementation:
Public class Quick3waySort implements SortTemplate {@ Override public void sort (Comparable [] array) {quickSort (array, 0, array.length-1);} @ SuppressWarnings ("unchecked") private void quickSort (Comparable [] array, int lo, int hi) {if (lo > = hi) {return;} int lt = lo, I = lo + 1, gt = hi; Comparable el = array [lo] While (I 0) {exch (array, lt++, iTunes +);} else if (tmp < 0) {exch (array, I, gt--);} else {ionization;}} quickSort (array, lo, lt-1); quickSort (array, gt + 1, hi) }} at this point, I believe you have a deeper understanding of "how to implement and optimize the fast sorting algorithm". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 308
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.