算法学习的第一天
算法学习之快速排序
快速排序采用分治的思想。
它的基本思想是:选择一个分界点,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
一般快速排序的使用有以下几个步骤:
①确定分界点。一般分界点的确定方式为:左边界 l; 右边界 r ; 中间值。 常采取左边界确定分界点的方法;
②调整区间。将整个数组调整成为两个区间。第一个区间中所包含的元素都小于等于分界点;另一个区间中所包含的元素都大于等于分界点;退出之后,该基准就处于数列的中间位置。
③递归处理左右两个区间,使其成为一个有序序列。
在调整区间这一步中,通用的方法为
①开两个数组a[ ],b[ ];
②原数组中的元素进行遍历。元素小于等于分界点的,就存在a[ ]数组中;元素大于分界点的,就存在b[ ] 数组中;
③遍历结束,分别对a[ ],b[ ]数组排序,排序结束后进行合并。
笔者学习的快速排序则是引用两个指针 i ,j 处理步骤②。
函数代码
void quick_sort(int q[] , int l ,int r) //定义一个函数quick_sort 其中q[]为原数组,l为q[]的左边界,r为q[]的边界
{ if(l >= r) return ; //如果左边界大于等于右边界,跳出函数
int x = q[l],i = l - 1 , j = r +1; //定义x为分界点(左边界),定义两个指针i,j i指针为左指针,j指针为右指针
while(i < j) //当i的值小于j的值时
{
do i++ ; while(q[i] < x); //如果当前i所代表的元素小于分界点,那么i则向右前进一位,否则停止
do j-- ; while(q[j] > x);//如果当前j所代表的元素大于分界点,那么j则向左前进一位,否则停止
if(i < j) swap(q[i],q[j]); //当i,j最终停下时,i代表的元素小于j代表的元素,那么i,j两个元素交换位置
} //最终,分界点左边的元素都小于分界点;分界点右边的元素都大于分界点。
quick_sort(q ,l ,j); //第一次排序的是分界点左边的元素
quick_sort(q , j + 1 , r);//第二次排序的是分界点右边的元素
}
快速排序是不稳定的算法,它不满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!
快速排序平均时间复杂度O(N*lgN)
标签:分界点,边界,元素,数组,排序,快速,指针 From: https://www.cnblogs.com/litershry/p/17009103.html