前言

关于排序算法，个人已经学习了前三种人称乌龟速三兄弟的算法

  • 冒泡排序

  • 选择排序

  • 插入排序

下面就是快速排序算法啦~

快速排序（quick_sort）

从数列中挑出一个元素，称为 “基准”（pivot）
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序

个人基于原理的c语言代码：

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
#include<stdio.h>
void quick_sort(int data[],int left,int right); 
int get_mid(int data[],int l,int r);
int main(){
	int i;
	int data[9]={3,4,1,6,2,8,7,9,5};
	quick_sort(data,0,9);
	for(i=0;i<9;i++)
		printf("%d ",data[i]);
	return 0;
}
void quick_sort(int data[],int left,int right){
	int mid;
	if(left<right)/*当左右指针都相等时，说明找到了位置*/{
		mid=get_mid(data,left,right);
		quick_sort(data,left,mid-1);//左排序 
		quick_sort(data,mid+1,right);//右排序 
	}	
}
int get_mid(int data[],int l,int r){
	int tmp=data[l];//默认将第一个数作为基准值，此时可看作第一个数已被拿出 
	while (l<r){
		while(l<r&&data[r]>=tmp)r--;//从右开始找 
		data[l]=data[r];//如果找到一个数比tmp小，将其放入空位此时的r位置空出 
		while(l<r&&data[l]<=tmp)l++;//同理从左找 
		data[r]=data[l];//如果找到一个数比tmp大，将其放入空位此时的l位置空出
	}//循环结束后所有比基准值大的都在右侧，比基准值小的都在左侧 
	data[l]=tmp;//此时左右指针相等，指向中间值，tmp赋值; 
	return l;//返回左指针位置，以此为界便于二分递归。 
}