快速排序是一种不稳定排序,它的时间复杂度为O(n·lgn),最坏情况为O(n2);空间复杂度为O(n·lgn)。
这种排序方式是对于冒泡排序的一种改进,它采用分治模式,将一趟排序的数据分割成独立的两部分,其中一组数据的每个值都小于另一组。每一趟在进行分类的同时实现排序。
其中每一趟的模式通过设置key当基准元素,key的选择可以是数据的第一个,也可以是数据的最后一个。这里以每次选取数据的第一个为例:
具体代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<stdio.h>
#define N 6
int fun( int arr[], int low, int high)
{
int key;
key=arr[low];
while (low<high)
{
while (low<high && arr[high]>=key)
high--;
if (low<high)
arr[low++]=arr[high];
while (low<high && arr[low]<=key)
low++;
if (low<high)
arr[high--]=arr[low];
}
arr[low]=key;
return low;
}
void quick_sort( int arr[], int start, int end)
{
int pos;
if (start<end)
{
pos=fun(arr,start,end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
}
int main()
{
int i;
int arr[N]={32,12,7,78,23,45};
for (i=0;i<N;i++)
{
printf ( "%d " ,arr[i]);
}
printf ( "\n" );
quick_sort(arr,0,N-1);
for (i=0;i<N;i++)
{
printf ( "%d " ,arr[i]);
}
return 0;
}
|
由于是第一次撰写博客,许多地方没有一个良好的习惯,还请读者见谅。创建这个博客的目的实际上是为了让自己对于数据结构与算法加深印象,通过博客的形式展现出来一方面方便自己查阅,另一方面以希望能够通过自己的微薄之力帮助到有需要的朋友。
也希望自己能够坚持下去,认真的去做这么一件事。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_39630587/article/details/76236562