快速排序中心思想
百度描述->
快速排序算法通过多次比较和交换来实现排序,其排序流程如下 (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
总结->
基本思想
**1选定中心轴
2将大于中心轴的数字放在中心轴的右边
3将小于中心轴的数字放在中心轴的左边
4分别对左右子序列重复前三步操作**
快速排序操作实现
这边我就用C语言实现了>>
//L为要排序的起始下标,R为数组要排最后元素的下标
void QuickSort(int arr[], int L, int R)
{
if (L >= R) //设定结束条件
return;
int right = R; //另设变量存储数组的起始位置和末尾
int left = L;
int point = arr[L];//选定中心轴
while (left < right)
{
while (left < right && point <= arr[right])
{ //在left<right条件下,把比中心轴大的放在右边,小的放在左边
right--; //如果本身比中心轴大的数就在中心轴右边,则继续移动right
}
if (left < right) //如果跳出上面循环,则一定是因为right指向的值比中心轴小,则需要把它移动到左边
{
arr[left++] = arr[right];
}
while (left < right && point > arr[left])
{
left++;//如果本身比中心轴小的数就在中心轴左边,则继续移动left
}
if (left < right)//同样如果跳出上面循环,则一定是因为left指向的值比中心轴大,则需要把它移动到右边
{
arr[right--] = arr[left];
} //最后两数移动到同一位置,就把刚才选中心轴的数放在这位置上
arr[left] = point;
}
//上面已经进行一次排序,分成两组,一组比中心轴大,在左边,一组比中心轴小,在右边
QuickSort(arr, L, right - 1);//递归将左边的进行排序
QuickSort(arr, right + 1, R);//递归将右边的进行排序
}
调用一下函数
int main()
{
int arr[10] = { 2,1,4,3,9,6,5,7,8,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
Quicksort(arr,0,sz-1);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
运行结果>
完事!!