快速排序 Quick Sort

快速排序 Quick Sort

快速排序也算是很出名的一种算法了,虽然说是不稳定的,但在各类面试笔试中出现的频率相当高。并且相较一些排序算法来说,快速排序的核心思路也比较简单:

  1. 挑选一个数target(一般为第一个),经过一次遍历比较后,将比此数小的,放在其前面,比此数大的,放在其后面。此数的前后序列都是无序的。此过程通常称为分区(partition)。其中交换的逻辑是比较重要的,具体为:有一个指针index指向第二个数,并且从第二个开始(第一个为target,不参与)遍历,如果比选定数小,则index后移,并且交换indexi;如果比选定数大,则直接进入下一次循环。
  2. 整个循环完成后,最后交换targetindex
  3. 则此被挑选的数的位置就确定了,然后再递归排序前后两个无序的数组即可。

快速排序

int[] array = {49, 38, 65, 97, 76, 13, 27, 50, 78, 34, 12, 64, 1};
quickSort(array, 0, array.length - 1);
static void quickSort(int[] array, int startPos, int endPos) {
    if (endPos > startPos) {  // 设置终止条件
        int target = array[startPos];  // 保存目标中间数
        int index = startPos;  // 设置索引位置
        for (int i = startPos + 1; i <= endPos; i++) {
            if (array[i] < target) {  //  如果遍历数小于目标数,则将其与索引下一位进行交换
                index++;
                int temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
        }
        array[startPos] = array[index];  // 遍历结束后,将中间的索引数与起始的目标中间数进行交换
        array[index] = target;
        quickSort(array, startPos, index - 1);  // 继续排序中间数前后的数组
        quickSort(array, index + 1, endPos);
    }
}

记得之前关于交换的算法是大小来回换,容易理解但代码量稍大一点,这种交换方法可能有点难理解,注意核心思想就是index记录了可被交换的位置,在遍历时比target大的都不管,即当前index指向的都默认是比target大的数,当遍历到比target小的数时,将两个进行交换,从而做到小的在前大的在后。

发表评论