快速排序理解

快速排序算法核心思想,取待排序序列中的某个元素作为分区点,大于分区点的元素挪到分区点右边(从小到大排序),小于分区点的元素挪到分区点左边。然后分区点左右两边的子序列循环以上操作,直至子序列长度为 1

左右指针法实现思路

1、首先定义分区点(pivot)pp 一般为数组 a 的第一个元素或最后一个元素 2、然后定义左(l)、右(r)两个指针分别指向数组的第一个元素(a[0])和最后一个元素 (a[a.length - 1]) 3、如果 a[l] > a[p]l、p 下标元素互换,l 前进 1 位 4、如果 a[r] < a[p]r、p 下标元素互换,r 后退 1 位 5、如果 l >= r,排序结束

Read more →

堆排序理解

堆排序的关键是构建大(小)顶堆,堆顶元素就是最大(小)的元素,然后堆顶元素和末尾元素交换位置,再次堆化除最后一个元素外的其它元素,循环次过程即可完成排序。

翻译成代码如下:

public void sort(int a) {
    for(int i = a.length - 1; i > 0; i--) {
        buildHeap(a, i);
        // 堆顶元素和最后一个元素交换,除过最后一个元素外其它元素再次构建大顶堆
        swap(a, 0, i);
    }
}
Read more →