推荐慕课网,刘宇波老师《算法与数据结构》
链接:http:
quickSort 课堂笔记
#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;
template<
typename T>
int partition(T arr[],
int l,
int r)
{
swap(arr[l],arr[rand()%(r-l+
1)+l]);
T v = arr[l];
int j = l;
for(
int i = l+
1;i <= r;i++){
if(arr[i] < v){
j++;
swap(arr[j],arr[i]);
}
}
swap(arr[l],arr[j]);
return j;
}
template<
typename T>
void _quickSort(T arr[],
int l,
int r)
{
if(l < r){
int p = partition(arr,l,r);
_quickSort(arr,l,p-
1);
_quickSort(arr,p+
1,r);
}
}
template<
typename T>
void quickSort(T arr[],
int n)
{
srand(time(NULL));
_quickSort(arr,
0,n-
1);
}
int main(){
int arr[] = {
9,
8,
7,
6,
5,
4,
3,
2,
1};
int n =
sizeof(arr)/
sizeof(arr[
0]);
quickSort(arr,n);
for(
int i =
0;i<n;i++)
printf(
"%d ",arr[i]);
printf(
"\n");
return 0;
}
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
template<
typename T>
int partition2(T arr[],
int l,
int r)
{
swap(arr[l],arr[rand()%(r-l+
1)+l]);
T v = arr[l];
int i = l+
1,j = r;
while(
true){
while(i <= r && arr[i] < v) i++;
while(j >= l+
1 && arr[j] > v) j--;
if(i > j)
break;
swap(arr[i],arr[j]);
i++,j++;
}
swap(arr[l],arr[j]);
return j;
}
template<
typename T>
void _quickSort2(T arr[],
int l,
int r)
{
if(l < r){
int p = partition2(arr,l,r);
_quickSort2(arr,l,p-
1);
_quickSort2(arr,p+
1,r);
}
}
template<
typename T>
void quickSort2(T arr[],
int n)
{
srand(time(NULL));
_quickSort2(arr,
0,n-
1);
}
int main(){
int arr[] = {
9,
8,
7,
6,
5,
4,
3,
2,
1};
int n =
sizeof(arr)/
sizeof(arr[
0]);
quickSort2(arr,n);
for(
int i =
0;i<n;i++)
printf(
"%d ",arr[i]);
printf(
"\n");
return 0;
}