当前位置:网站首页>Quick sort (C language)
Quick sort (C language)
2022-07-04 10:27:00 【Lol only plays Timo】
There are many sorts , For example, Hill sort , Bubble sort , Heap sort … … There are many kinds of , Today I want to talk about the Quicksort with the lowest time complexity .
First, let's learn about the manual process of quick sorting :
With the understanding of this manual process , The code is ready , We can write an exchange function first :
void swapOnce(int *array, int start, int end) {
int i = start;
int j = end;
int temp = array[i];
if (i >= j) {
return;
}
while (i < j) {
while (i < j && array[j] > temp) {
j--;
}
if (i < j) {
array[i++] = array[j];
}
while (i < j && array[i] < temp) {
i++;
}
if (i < j) {
array[j--] = array[i];
}
}
array[i] = temp;
swapOnce(array, start, i - 1);
swapOnce(array, i + 1, end);
}
The last two lines of this exchange function are actually the idea of recursion , Because after the first overall exchange , that temp In fact, the whole array is divided into two sub arrays , The work to be done in the two sub arrays is actually the same as that of this large array , So just call this exchange function again .
The following is the array generation and the complete code of this quick sort :
#include <stdio.h>
#include <malloc.h>
#include <time.h>
int *creatArray(int minValue, int maxValue, int count);
void showArray(int *array, int count);
void swapOnce(int *array, int start, int end);
void quickSort(int *array, int count);
void quickSort(int *array, int count) {
swapOnce(array, 0, count-1);
}
void swapOnce(int *array, int start, int end) {
int i = start;
int j = end;
int temp = array[i];
if (i >= j) {
return;
}
while (i < j) {
while (i < j && array[j] > temp) {
j--;
}
if (i < j) {
array[i++] = array[j];
}
while (i < j && array[i] < temp) {
i++;
}
if (i < j) {
array[j--] = array[i];
}
}
array[i] = temp;
swapOnce(array, start, i - 1);
swapOnce(array, i + 1, end);
}
void showArray(int *array, int count) {
int index;
for(index = 0; index < count; index++) {
printf("[%d] ",array[index]);
}
printf("\n");
}
int *creatArray(int minValue, int maxValue, int count) {
int index;
int value;
int *array;
srand(time(0));
array = (int *) calloc(sizeof(int), count);
for (index = 0; index < count; index++) {
value = rand() % (maxValue - minValue + 1) + minValue;
array[index] = value;
}
return array;
}
int main() {
int *array = NULL;
int maxValue;
int minValue;
int count;
printf("please input minValue/maxValue/count:");
scanf("%d%d%d", &minValue, &maxValue, &count);
array = creatArray(minValue, maxValue, count);
printf("before sorting:\n");
showArray(array, count);
printf("after sorting:\n");
quickSort(array, count);
showArray(array, count);
free(array);
return 0;
}
Let's take a look at the running result of this function :
If you generate a function for the array in this code , Or if you have any questions about this code, you can leave a message below , Or believe me .
边栏推荐
- Dynamic memory management
- IPv6 comprehensive experiment
- uniapp 处理过去时间对比现在时间的时间差 如刚刚、几分钟前,几小时前,几个月前
- Exercise 9-3 plane vector addition (15 points)
- Rhcsa12
- What is devsecops? Definitions, processes, frameworks and best practices for 2022
- 2021-08-10 character pointer
- MPLS: multi protocol label switching
- System. Currenttimemillis() and system Nanotime (), which is faster? Don't use it wrong!
- Press the button wizard to learn how to fight monsters - identify the map, run the map, enter the gang and identify NPC
猜你喜欢
If the uniapp is less than 1000, it will be displayed according to the original number. If the number exceeds 1000, it will be converted into 10w+ 1.3k+ display
Vs201 solution to failure to open source file HPP (or link library file)
IPv6 comprehensive experiment
How can Huawei online match improve the success rate of player matching
leetcode1-3
【Day1】 deep-learning-basics
183 sets of free resume templates to help everyone find a good job
Development guidance document of CMDB
Application of safety monitoring in zhizhilu Denggan reservoir area
Time complexity and space complexity
随机推荐
Rhcsa - day 13
Read a piece of text into the vector object, and each word is stored as an element in the vector. Convert each word in the vector object to uppercase letters. Output the converted elements in the vect
按键精灵打怪学习-识别所在地图、跑图、进入帮派识别NPC
【Day2】 convolutional-neural-networks
Exercise 7-8 converting strings to decimal integers (15 points)
Velodyne configuration command
转载:等比数列的求和公式,及其推导过程
【FAQ】华为帐号服务报错 907135701的常见原因总结和解决方法
使用 C# 提取 PDF 文件中的所有文字(支持 .NET Core)
Realsense of d435i, d435, d415, t265_ Matching and installation of viewer environment
Exercise 9-4 finding books (20 points)
Remove linked list elements
MongoDB数据日期显示相差8小时 原因和解决方案
Introduction to tree and binary tree
From programmers to large-scale distributed architects, where are you (2)
Static comprehensive experiment ---hcip1
Custom type: structure, enumeration, union
Batch distribution of SSH keys and batch execution of ansible
Four characteristics and isolation levels of database transactions
Online troubleshooting