回顾冒泡排序、快速排序,直接选择排序以及递归思想。快速排序和二分查找都融入了分而治之的思想,一分再分,递归之。
1、冒泡排序
相邻元素之间逐对两两比较,若不符合预期则先交换位置再继续比较,如此,每次比较都能把最大或最小的元素放在预期位置,直到完成排序。
2、快速排序
1、准备工作:先选定一个参考值,设置两个指针(设为i,j,分别指向数字序列的头和尾)。
2、同时从数字序列的两头进行扫描对比,将大于参考值的数字都放于参考值的一侧,小于参考值的数字置于另一侧。直到i,j指向同一个位置,这个位置即为参考值的预期位置,设为m。
3、对大于参考值一侧,令i=m+1,对小于参考值的一侧,令j=m-1。再分别对参考值的两侧重复步骤1、2。
4、重复步骤1、2、3,直到i>j。
public static int getMiddle(int[] array, int i, int j)
{
int key = array[i];
while(i<j)
{
//从前向后扫描
while (i<j && array[j]>key)
{
j--;
}
array[i] = array[j];
//从后向前扫描
while (i<j && array[i]<key)
{
i++;
}
array[j] = array[i];
}
array[j] = key;
return j;
}
//递归的思想,反复划分,直到只剩一个元素。
public static void qSort(int[] array, int i, int j)
{
if(i<j)
{
int middle = getMiddle(array, i, j);
qSort(array, i, middle-1);
qSort(array, middle+1, j);
}
}
3.选择排序
就像打擂台,把元素一个一个往擂台上摆,优胜劣汰,从而确定第一名,第二名,第三名。。。直到排序完成。
4、二分查找算法
要求,序列是有序的,思想与快速排序类似,也运用了分而治之。
记得应用递归时,return,否则会一直执行到return -1,结束,导致输出始终为-1.