Write in the front

This article , Let's talk about sorting algorithms , We've talked about it before Simple insert sort and ta Optimized version of Shell Sort , In this section, we will contact a more “ senior ” Algorithm. -- Quick sort .

In the valley of Los Angeles , Encountered a card optimization problem , If you don't optimize the fast platoon , There will be several points TLE Of , Later, we can do all kinds of optimization around this problem , Let's start with quick sort .

Ideas

If our computer could run every second 10 100 million times , So right. 1 Hundreds of millions of them , bucket Sorting only needs 0.1 second , and Bubbling Sorting requires 1 Ten million seconds , achieve 115 It's been a long time , Isn't it scary ? Is there a sort algorithm that can be faster without wasting space ? That's it “ Quick sort ”!

Suppose we're right now “** 6 1 2 7 9 3 4 5 10 8” this 10 Number to sort . First of all, find any number in the sequence as the base number ( Don't be frightened by this term , This is a number for reference , You'll know what it's used for later ). For convenience , Just let the first number 6 As a benchmark . Next , You need to put all... In this sequence Larger than the reference number The number of is placed in 6 Of On the right , Than The reference number is small The number of is placed in 6 Of On the left **, It's like this arrangement .

3 1 2 5 4 6 9 7 10 8

In the initial state , Numbers 6 At the end of the sequence 1 position . Our goal is to 6 Move to a position in the middle of the sequence , Suppose this position is k. Now we need to find this k, And take The first k position It's the dividing point , All the numbers on the left are less than or equal to 6, The numbers on the right are greater than or equal to 6.

The method is actually very simple : From the initial sequence “ 6 1 2 7 9 3 4 5 10 8” Start at both ends “ Probe ”. First find a smaller one from right to left 6 Number of numbers , And then go from left to right and find one greater than 6 Number of numbers , And then exchange them . You can use it here Two variables i and j, Point to the left and right of the sequence respectively . Let's give these two variables a nice name “ sentry i” and “ sentry j”. At the beginning, let the sentry i To the far left of the sequence ( namely i=1), Point to numbers 6. Let the sentry j To the far right of the sequence ( namely j=10), Point to numbers 8.





Picture source : 《 AHA algorithm 》

Complete flow chart

If mid Take the leftmost word , When itself is in order , Will become a bubble sort , become n square

( Example ) Luogu 1177 Quick sort

https://www.luogu.com.cn/problem/P1177

Wrong version

No optimization , Order will TLE

#include <iostream>
#include<cstdio>
int a[1000001];// Define global variables , These two variables need to be used in the subfunction void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
} // Recursive method
void quicksort(int left, int right) {
// For example, it can be concluded that if the left is greater than or equal to the right, it will return to ?
// Greater than is :index just ==right, And then we're going to (index+1,right)
if (left >= right) {
return;
}
// Default datum index It's the one on the far left , And i Start on the left ,j From the right
int i = left, j = right, index = left; // refactoring
// The big premise , The two didn't meet
while (i != j) {
// You have to judge i<j, Because the big premise outside , It may destroy
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
// if i,j Haven't met yet
if (i < j) {
swap(&a[i], &a[j]);
}
}
// When you come out i,j Must meet
swap(&a[i],&a[index]);
// take i Assigned to datum
index = i; quicksort(left, index - 1);
quicksort(index + 1, right);
}

First get mid, Then let the left heel mid In exchange for

Because it is a unilateral search , The last two points are TLE

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
void swap(int arr[], int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void QuickSort(int arr[], int left, int right)
{
int i, pivot; if (left >= right)
return;
pivot = left;
swap(arr, left, (left + right) / 2);
for (i = left + 1; i <= right; i++) // Unilateral search , This can be a two-way search
if (arr[i] < arr[left])
swap(arr, i, ++pivot);
swap(arr, left, pivot);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
int main()
{
int n;
int *arr;
int i; scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * (n + 1));
for (i = 1; i <= n; i++)
scanf("%d", arr + i); QuickSort(arr, 1, n);
for (i = 1; i <= n; i++)
printf("%d ", arr[i]);
return 0;
}

Improved to bilateral search

Just the last point TLE 了 , And the last point , just Constant column The situation of

#include <iostream>
#include<cstdio>
int a[100010];// Define global variables , These two variables need to be used in the subfunction void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
} // Recursive method
void quickSort(int left, int right) {
// For example, it can be concluded that if the left is greater than or equal to the right, it will return to ?
// Greater than is :index just ==right, And then we're going to (index+1,right)
if (left >= right) {
return;
}
// Default datum index It's the one on the far left , And i Start on the left ,j From the right
int i = left, j = right, index ;
int mid=(left+right)/2;
swap(&a[left],&a[mid]);
index=left; // refactoring
// The big premise , The two didn't meet
while (i != j) {
// You have to judge i<j, Because the big premise outside , It may destroy
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
// if i,j Haven't met yet
if (i < j) {
swap(&a[i], &a[j]);
}
}
// When you come out i,j Must meet
swap(&a[i],&a[index]);
index = i; quickSort(left, index - 1);
quickSort(index + 1, right);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort(0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}

replay mid( Consider the constant column )

You haven't hit the triple yet , Pick up to mid If it is the smallest, it will degenerate to bubbling n square

#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
// Exchange element positions
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void quickSort(int* arr, int low, int high) {
// If the length does not meet the requirements , Go straight back to
if (low >= high) {
return;
}
int left = low;
int right = high;
// Select the middle as the benchmark , Note that take the middle value , Instead of Subscripts , Because the subscript may change in subsequent exchanges
// such as left Go to the mid here , and right It stopped mid On the right , Then I will exchange ,arr[mid] It's changed
int mid = arr[(low + high) >> 1];
while (left <= right) {
// Notice that it's less than , If it is less than or equal to , The constant column will always left Move , and right Don't move , Become n square
while (arr[left] < mid) {
left++;
}
// Also note that it is greater than
while (arr[right] > mid) {
right--;
}
// Note here that it is less than or equal to , For convenience left and right Jump directly to the left and right of the hub
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
// Recursively call
//right At the end of interval one
quickSort(arr,low, right);
//left Went to the head of interval two
quickSort(arr, left, high);
}
int main()
{
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a[i];
}
quickSort(a,1,n);
for (i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}

flow chart

From here mid yes 60

here left and right Have met

  • then left Find that the conditions are not met ,86>mid(60),left still 86

    • right Meet the conditions ,right Go to --, Go to the 15 Stop there
  • then left dissatisfaction <=right, Just start recursion
    • Recursive interval ① yes : [42,15] ( Are less than or equal to 60)
    • Section ② yes : [86,68] ( Greater than or equal to 60)
		while (arr[left] < mid) {
left++;
}
// Also note that it is greater than
while (arr[right] > mid) {
right--;
}
// Note here that it is less than or equal to , For convenience left and right Jump directly to the left and right of the hub
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
// Recursively call
//right At the end of interval one
quickSort(arr,low, right);
//left Went to the head of interval two
quickSort(arr, left, high);

problem

Because I didn't put the hub in the right position , As a result, the length of the finally separated interval will be one more element : Pivot ( Will this affect time efficiency )

If you test with a certain amount of data , The gap in time efficiency is not very big .

** Combine three numbers to take the middle ( Temporary God )

#include<cstdio>
#include<iostream>
#include"RcdSqList.h"
using namespace std;
//int a[100010];
// Exchange element positions
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Take the three Numbers
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort(int* arr, int low, int high) {
// If the length does not meet the requirements , Go straight back to
if (low >= high) {
return;
}
int left = low;
int right = high;
// Select the middle as the benchmark , Note that take the middle value , Instead of Subscripts , Because the subscript may change in subsequent exchanges
// such as left Go to the mid here , and right It stopped mid On the right , Then I will exchange ,arr[mid] It's changed
// Call triple fetch , Get the middle number
int mid = arr[getmid(arr, low, high)];
while (left <= right) {
// Notice that it's less than , If it is less than or equal to , The constant column will always left Move , and right Don't move , Become n square
while (arr[left] < mid) {
left++;
}
// Also note that it is greater than
while (arr[right] > mid) {
right--;
}
// Note here that it is less than or equal to , For convenience left and right Jump directly to the left and right of the hub
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
// Recursively call
//right At the end of interval one
quickSort(arr, low, right);
//left Went to the head of interval two
quickSort(arr, left, high);
}
int main()
{
int n, i;
/*cin >> n;*/
/*for (i = 1; i <= n; i++)
{
cin >> a[i];
}*/
int a[100] = { 0,42 ,90,30,86,42,15,57,20 };
quickSort(a, 1, 8);
for (i = 1; i <= 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
}

summary

Finally, download the test points , Then I read the blog , Find the reason for the timeout , It's actually completely orderly

Then take the standard answer debug once , Finally found the difference , It's the constant column when both of them move , I'm just a mobile , It degenerates into n Squared

Be careful

want < No, not <=

** To enlarge the problem , such as j Go straight to the left , Zoom in until you walk all the way i Where are you going !

The feeling from watching the dark horse video ....

The problem is very serious , Will become n square

If you put the benchmark to the far left , If it is in order, it will time out

xxxx Pivot to choose the value with the middle size , To solve a completely orderly situation ( Get three out of three .)

  • Note that taking the middle value here does not mean taking the middle value of the interval , But the size is Head and tail and Interval median Three values are arranged In the middle the

    • If you take the value in the middle of the interval , It doesn't solve the problem of complete order , such as 5 4 1 2 3 , take mid be equal to 1, It's the smallest case again , Last mid Put it in the right place ( That is, the first position ), Recursion to his left and right , It doesn't have the effect of turning the original interval into two halves , Just got the section on the right , It's equivalent to just reducing one element ( similar Bubbling Just put an element in the right place )

Give Way left++ The condition should be < Number ! , Let me go after the exchange left++,right--, This solves the case of constant Columns

If we don't move after the exchange , that > You have to change it to >=, This will move , But it becomes a single pointer movement , Or degenerate into n Squared

After the exchange moves ,left and right It's just the beginning and end of two intervals

** Three way cutting method

https://www.luogu.com.cn/problem/P1177( It's still a template question )

Let's look at the code first

#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
// Exchange element positions
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Take the three Numbers
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort_2(int rcd[], int low, int high) {
if (low >= high) {
return;
}
// Call triple fetch , Get hub location
int pivot=getmid(rcd,low,high);
// Put the pivot value in low Location ( In exchange for )
swap(&rcd[low],&rcd[pivot]);
// The pivot value is equal to rcd[low]
int pivotVal = rcd[low];
//i Used to traverse an interval
int left, right, i;
// Traverse the interval directly from the next position of the hub
left = low, right = high, i = low + 1;
// Traverse the entire interval
while (i <= right) {
// If less than the hub value
if (rcd[i] < pivotVal) {
// You have to put it in front , Follow left In exchange for
swap(&rcd[i], &rcd[left]);
// After the exchange ,i In exchange for one i The value in front , It must have been compared , therefore i++
i++;
//left In exchange for one i The value of the original position , Also compared , therefore left++
left++;
}
// If greater than the hub value
else if(rcd[i]>pivotVal)
{
// You have to put it in the back , Follow right In exchange for
swap(&rcd[i], &rcd[right]);
//right In exchange for one i The value of the original position , Also compared , therefore right++
right--;
//i Immobility , Because it's the other one i The new value behind , I haven't compared }
// Equal to
else
{
i++;
}
}
quickSort_2(rcd, low, left - 1);
quickSort_2(rcd, right + 1, high);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort_2(a,0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}

Rough flow chart

Here, let's default that the pivot is the leftmost element , Easy to understand ( In the actual situation, press the code above to take the middle followed by the leftmost exchange )

Use one i To traverse this interval , I need one more left And a right The pointer

  • When rcd[i] Greater than the hub value , Like in the picture 90
  • When rcd[i] Less than the hub value , Like in the picture 20
  • When rcd[i] When equal to the pivot value , Like in the picture 42

See the text description in the figure for details

So in summary , If the position is a The value that has been compared with the hub value , Or change to a value that has been compared with the hub value ( It would be You need to update Check his pointer position )

advantage

  • Reduce the comparison of repeated elements , Because the repeating elements are already arranged as a single part in one sort , After that, you only need to sort other elements that are not equal to the repeating element .

At the end

  • here we are Quick line up here , In fact, it has involved some recursive Knowledge , Related to recursion is actually “ Binary search ”、“ Merge sort ” etc. , This column will also continue to update relevant knowledge , Welcome to study together !

Quick sort -- Loguca TLE Finally, I chose more related articles on three-way cutting

  1. Luogu P1119 Post disaster reconstruction shortest path +Floyd Algorithm

    Catalog Topic Topic link Title Description I / O format Input format Output format I/o sample sample input sample output explain Ideas AC Code summary Topic Topic link P1119 Post disaster reconstruction Title Description B Area after the earthquake , All villages ...

  2. Luogu ——P1119 Post disaster reconstruction

    P1119 Post disaster reconstruction Background B Area after the earthquake , All the villages have caused some damage , And the earthquake didn't affect the roads . But before the village is rebuilt , All roads to villages that have not been rebuilt are not open to traffic . let me put it another way , Only two heavy... Are connected ...

  3. Luogu 1119 Post disaster reconstruction Floyd

    More interesting Floyd, I didn't see it at first ....( I'm not very clear headed in the afternoon ) Think about it first Floyd Its implementation principle , for(k=1;k<=n;k++) for(i=1;i<=n;i++) for( ...

  4. Luogu P1119 Post disaster reconstruction [Floyd]

    Background B Area after the earthquake , All the villages have caused some damage , And the earthquake didn't affect the roads . But before the village is rebuilt , All roads to villages that have not been rebuilt are not open to traffic . let me put it another way , Only the road connecting the two reconstructed villages can ...

  5. Luogu [P1119] Post disaster reconstruction

    We find that every inquiry is for any two points , So this is a multi-source shortest path problem , Multi source shortest path , We first think of floyd, Because the time of inquiry is constant , So for every inquiry , We will the points that have not yet been relaxed k operation . #includ ...

  6. Luogu P1119 Post disaster reconstruction

    subject To do a replacement, we must first clarify the data range ,n<=200, explain n^3 Our algorithm can live , And this topic is obviously a graph topic , So it's easy for us to think that this problem can be used folyd, But when I was doing this problem, because I didn't have a deep ...

  7. Luogu P1119 Post disaster reconstruction Floyd + offline

    https://www.luogu.org/problemnew/show/P1119 It's really a story I did a similar problem in Ningxia six months ago , At that time, I lost the gold medal because of my ignorance . If you go now, you'll be safe , It's strange ...

  8. Luogu P1119 Post disaster reconstruction

    Portal The main idea of the topic : The point is destroyed ,t[i] For the first time i A little time to repair , And t[1]<t[2]<t[3].. A number of inquiries , Sort by time , Question no t moment ,u,v The shortest path length . Answer key :floyed Add points according to time ...

  9. Luogu P1119 Post disaster reconstruction ——Floyd

    subject :https://www.luogu.org/problemnew/show/P1119 N Very small , Consider using Floyd: because t It's in order , So add some one by one ,Floyd Update can : This also gives us an inspiration , If ...

  10. Luogu P1119 Post disaster reconstruction ——dijstra

    Let's start with the last wave of topics  https://www.luogu.org/problem/P1119 For this question, we can put the questions in chronological order Then, with the query, operate the corresponding points that have been successfully reconstructed Every time you update a point, run it again with him as the starting point dij ...

Random recommendation

  1. free translation :《JVM Internals》

    Language translator To deepen the understanding of JVM It's more convenient for you to understand and consult in the future , So we translate the original text . The content is based on my understanding of JVM On the basis of the understanding of translation , Plus my English level is limited , If there is any mistake, please correct it , thank you . Original address :http://blog.j ...

  2. github page and hexo Build an online blog

    Catalog : install node.js And git Commonly used git command install hexo To configure hexo hexo Publish to github 1. install node.js and git Tools https://nodejs.org/en/ Download an ...

  3. mysql How to modify the string to utf8

    1. Command line input mysl After the code , Then input status You can see the current encoding 2. Go to the installation directory X:\%path%\MySQL\MySQL Server 5.0\bin\MySQLInstanceConf ...

  4. 201521123025 《Java Programming 》 The first 2 Weekly learning summary

    1. Summary of this chapter Some attention : (1) stay JAVA in , Floating point numbers without suffixes are defaulted to double type , If you want to use float Type is to add... After the data f or F suffix , Such as float a=32.6f( correct );float a=32. ...

  5. android Broadcast installation specifies the downloaded apk

    // Broadcast out , The broadcast receiver processes the downloaded file   Intent sendIntent = new Intent("com.test.downloadComplete");    ...

  6. Swift How to simplify the lengthy class instance initialization code in the standard library

    Maybe some children's shoes don't know , stay Swift For any type of any static All members are effective . Let's actually write an example to see : import UIKit class CFoo{ static let share ...

  7. 【 PostgreSQL】 Query the distribution key information of all tables in a certain mode

    I want to see if the distribution keys created by all tables in a certain mode are reasonable , Look up the system table and spell it as follows sql, If you have a better one sql Or comments are welcome ! ​SELECT     aaa.nspname AS " Schema name ", ...

  8. Fall in love Linux(Fedora20)2—— install Java Running environment (JDK)

    because Fedora20 Bring their own OpenJDK, So let's delete our own : 1) View the current jdk situation # rpm -qa|grep jdk 2) uninstall openjdk # yum -y remove java ja ...

  9. 【jQuery Demo】 Picture waterfall flow implementation

    Waterfall stream is a website like a waterfall —— Rich website content , In particular, gorgeous pictures will make you linger . When you browse the website, you just need to gently slide the mouse wheel , All the wonderful pictures can be presented in front of you . Waterfall flow website is a new website model —— her ...

  10. Codeforces Round #536 (Div. 2) B. Lunar New Year and Food Ordering

    #include <bits/stdc++.h> #define N 300010 #define PII pair<int, int> using namespace std ...