[算法与数据结构] - No.3 快速排序

本文主要是介绍[算法与数据结构] - No.3 快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的排序码大小,将整个对象序列划分为左右两个子序列： 
左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 

右侧子序列中所有对象的排序码都大于基准对象的排序码

一趟快速排序的具体做法是：
设两个指针low和high，设枢轴记录的关键字为pivotkey。

首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止

QuickSort.cpp

#include <iostream>using namespace std;int partion(int arr[],int low,int high)
{//arr[0] = arr[low];while(low<high){while(low<high&&arr[high]>=arr[low])high--;int temp1 = arr[low];arr[low] = arr[high];arr[high] = temp1;while(low<high&&arr[low]<=arr[high])low++;int temp2 = arr[low];arr[low] = arr[high];arr[high] = temp2;}//arr[low] = arr[0];return low;
}int QuickSort(int arr[],int low,int high)
{int flag = partion(arr,low,high);if(low<high){QuickSort(arr,low,flag-1);QuickSort(arr,flag+1,high);}
}
int main()
{int n;int arr [1000];cin >> n;for(int i = 0 ; i < n; i++){cin>>arr[i];}int j,k;QuickSort(arr,0,n);for(int i = 0 ; i < n; i++){cout<<arr[i]<<" ";}return 0;
}

P.S.文章不妥之处还望指正

这篇关于[算法与数据结构] - No.3 快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---