冒泡排序,快速排序、选择排序及二分法查找思想回顾

时间:2022-12-23 22:12:16

回顾冒泡排序、快速排序,直接选择排序以及递归思想。快速排序和二分查找都融入了分而治之的思想,一分再分,递归之。

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.