最近在看数据结构，研究了一下常用的几种排序方法：1.冒泡排序，2.选择排序，3.插入排序，4.希尔排序，5.快速排序，6堆排序。
在这里进行简单总结一下，希望给大家一点帮助。完整的源码在文章最后。
一.冒泡排序
这个是是所有排序方法中最简单的，当然它花费的时间也是最高的。
将数组依次进行两两对比，如果后一个值大于前一个值，这两个值就相互交换，这样最大的数就被替换到最后的位置，实现大数冒泡。
// 冒泡排序
private static void bubbleSort(int[] arr) {
int size = arr.length;
// 外层循环，保证out之后的值 是按照从小到大顺序排列的。
for (int out = size - 1; out > 0; out --) {
// 内层循环，将最大的值移动到最后out位置，实现了大数冒泡
for (int in = 0; in < out; in++) {
if (arr[in] > arr[in + 1]) {
swap(arr, in, in + 1);
}
}
}
}
如代码所示：
- 外循环依次将out值依次递减。
- 内循环是寻找arr数组从 0--out下标中的最大值，将它替换到
out位置。
冒泡排序效率：当有N个元素的数组时，外循环要进行N次，内循环平均要
进行N/2次，那么总的循环次数是 N^2/2 次,它的执行时间是O(N^2)。
但是它的交换次数比较多，如果数据是随机的，那么平均有一半元素可能需
要交换，总的交换次数是 N^2/4 次。
注意：进行排序时，临界值怎么确定？那么我的建议是保证数组角标不越界，不要过度追求极限临界值，什么意思呢？
比如像冒泡排序，它内循环临界值不用确定，因为是外循环传来的。而有
arr[in] > arr[in + 1]这个表达式，所以out的从 size - 1开始的。
什么时候结束呢？因为一直要比较到arr[0] > arr[1],所以out最小的值是1，
当然你写out>=0也没有关系，当out==0的时候，in < out不成立，内循环直
接跳出。
但是千万不要写out > 1,这个是错误的，比方说对于{2,3,1}这个数组，它的
排序就不正确。
二.选择排序
选择排序和冒泡排序一样简单，但是它数据交换的次数比冒泡排序少的多。
使用循环，找到数组中最小值，替换到遍历起始位置。
// 选择排序
private static void selectSort(int[] arr) {
int size = arr.length;
// 外层循环，保证out之前的都是有序的
for(int out = 0; out < size; out ++) {
int mixIndex = out;
// 内层循环，找到out位置最小值
for (int in = out + 1; in < size; in++) {
if (arr[mixIndex] > arr[in]) {
mixIndex = in;
}
}
if (mixIndex != out) {
swap(arr, mixIndex, out);
}
}
}
如代码所示：
- 外循环将out值依次递增。
- 内循环找到从out位置开始到数组结束位置arr.length -1中最小值，和out位置的值进行交换。
可以看出选择和冒泡很像，它们的主要区别是：
- 选择排序在内循环的时候，只是寻找最值(最大值或者最小值)，不进行交换，而是在内循环结束时进行交换。
- 冒泡排序在内循环的时候，就进行交换，使得最值能够移动到末尾。
选择排序效率：和冒泡排序一样，它的总循环次数是 N^2/2 ，它的执行时间是O(N^2)。但是它的交换次数最多只有N次。
三.插入排序
这个排序的执行时间对于随机的数据排序效率比冒泡和选择排序都少，但是对于极端数据(比如说完全倒序的数据)可能没有选择好，交换的次数过多了。
默认out位置之前(不包括out)的元素都是有序的。
- 对于out位置的元素，要先与out之前的元素依次进行比较。
- 找到应该插入的位置in,将in位置之后(不包括in)的数据全部右移一位.
- 再将in位置存放out位置原来的值。这样就实现了插入之后的前out(包括out)的数组还是有序的。
// 插入排序
private static void insertSort(int[] arr) {
int size = arr.length;
// out之前的是有序的，所以第0位置是有序的，然后将后面的数据插入到这个局部有序数组对应位置
for(int out = 1; out < size; out++) {
// 记录下out位置的值，将它替换至正确的位置
int temp = arr[out];
int in = out;
// arr[in - 1] <= temp 表示temp就应该插入in位置，
// 因为temp比in+1位置的元素小，但是又比in-1位置元素大(包括等于)
while(in - 1 >= 0 && arr[in - 1] > temp) {
arr[in] = arr[in - 1];
in --;
}
if (in != out) arr[in] = temp;
}
}
外循环从1开始，第0位置的元素肯定是有序的(因为就它一个值)，接下来将1到arr.length-1的元素依次插入到这个局部有序数组正确位置，
内循环进行递减循环比较，找到out位置的元素在局部有序数组中正确的位置。
我们要在数组中插入一个元素，那么从被插入位置开始，之后的值都要右移一位，那我们必须进行递减循环(从大到小),这样才能实现前一个位置元素覆盖后一个位置的元素。同理如果删除一个元素，就必须递增循环，实现后一个位置元素覆盖前一个位置元素。
插入排序效率：外循环要进行N次，内循环如果是最极端的情况(数组是倒序的),那么进行的次数就是1到N次，平均就是N/2次，如果是随机数据的话，那么平均次数就是N/4，所以它的总循环次数是N^2/4 到 N^2/2 次，它的执行时间也是O(N^2)。但是它的交互次数和循环次数一样多。
四.希尔排序
希尔排序是建立在插入排序基础上的。它解决了插入排序的一个问题。
考虑一种情况，对于一个随机数组，如果有很小的数据在最右端的位置，那么要将它移动到最左端位置，需要进行很多次内循环，因为我们每次的循环间隔是1。
那么有没有一种方式，可以使一些右端位置较小的值，快速移动到左端位置呢？希尔排序就是解决这个问题的。
但是注意希尔排序对极端数据(完全倒序数组)没有什么优化。
private static void shellSort(int[] arr) {
int size = arr.length;
int h = 1;
while(h <= size / 3) {
// 这里加1是保证h = (h - 1) / 3最后一个值是1，
h = h * 3 + 1;
}
while (h > 0) {
for(int out = h; out < size; out++) {
int temp = arr[out];
int in = out;
// arr[in - h] <= temp 表示temp就应该插入in位置，因为temp比in-h位置的值大，又比in+h位置的值小
while(in - h >= 0 && arr[in - h] > temp) {
arr[in] = arr[in - h];
in = in - h;
}
if (in != out) arr[in] = temp;
}
h = (h - 1) / 3;
}
}
如代码所示,希尔排序与插入排序相比较，最主要的变化有两点：
- 在内循环中每次步长不在是1了，而是一个h, 这个值开始很大，这样就可以将较小的值，进行大跨越式地向前移动。
- 多加了一个最外层循环，它逐渐递减步长h的值。注意这个h的选择，它必须保证最后一次递减的值是1， 这样才能在内循环中，保证每个值都进行过比较了。
注意：对于中间循环for(int out = h; out < size; out++)，千万不要用out = out + h替代out++， 这个并不是优化循环，减少循环次数，它实际上会导致很多较小数没有没法移动到大跨越地移动到左边。
因为这些较小的数，因为它们在out+h的间隔之外，所以根本没有办法进入内循环进行比较，从而进行大跨越地移动。这样就导致了希尔排序失去了作用，变成和插入排序一样的效率。
至于h = h * 3 + 1这个数学家研究出来的间隔序列。为什么这个间隔序列可以提高效率，具体原理我肯定是说不清楚的。
希尔排序效率：没有办法从理论上分析出希尔排序的效率，对于随机数据，它的执行时间大概是O(N*( log N)^2)。
五.快速排序
快速排序是常用排序算法中效率最高的，不过在讲快速排序之前，先要说说它用到的一个算法，划分算法。
划分算法
对于一个随机数组，找到一个关键值pivot，通过划分算法，使得index位置之前的数据都不大于pivot，index位置之后的数据都不小于pivot。
通过两个指针left和right(代表数组最左端和最右端的位置)。
- 先将left自增，如果arr[++left]比pivot大，就说明left这个位置的值需要交换。
- 将right自减，如果arr[--right]比pivot小,那么right位置的值要进行交换。
- 将这个right和这个left位置的值进行交换，一直到left>=right循环结束。
private static int partition(int[] arr, int pivot) {
// 将left开始设置为-1，因为下面判断使用arr[++left]，会先自增。
// 如果使用arr[left++]，那么进行判断arr[++left] < pivot时的left值
// 和进行交换swap(arr, left, right)就不是同一个值了。
int left = -1;
// 同left一样，比真实坐标大一的位置
int right = arr.length;
while (left < right) {
//这里;表示空语句，只有不满足条件，循环跳出。
while (left < right && arr[++left] < pivot);
while (left < right && arr[--right] > pivot);
swap(arr, left, right);
}
return right;
}
这里可能有疑惑，为什么我们在while (left < right)中已经判断了条件，还要在内循环中继续判断这个条件呢？
考虑一种情况，如果数组中的元素都比pivot小，那么left一直自增，然后角标越界，所以while (left < right && arr[++left] < pivot)中left < right只是防止角标越界的。
但是while (left < right && arr[--right] > pivot)就不止如此了：
- 作用一是防止角标越界。
- 作用二保证right位置的值都是不小于pivot。
这是怎么回事呢？考虑一下第一个内循环在什么情况下，会跳出循环，left >= right或者arr[left] >= pivot。
- 当left >= right时候，那么也会直接跳出第二个内循环。
- 当arr[left] >= pivot时，如果arr[--right]<=pivot，就会和left位置进行交换，保证right位置的值都是不小于pivot。这一点是实现划分算法的关键。
当然只有一种情况下是例外的，那么就是数组中所有元素都比pivot，那么right位置的值也小于pivot。
这里可能还有个疑惑，如果我们循环条件使用arr[++left] <= pivot和arr[--right] >= pivot，这样可以减少交换次数，不是更好么？
对于划分算法本身来说，这样的确没关系，而且的确更好。但是对于快速排序的话，这样的效果就非常差了。
当我们使用这种判断条件时，的确会减少交换次数，但是它也会导致，划分之后所找到的那个位置会在数组的最后端或者最左端附近，因为满足交互条件变少，left或者right倾向于边缘位置，而不是中间位置。
这样会导致我们快速排序的时候，进行更多地递归，影响效率，严重时堆栈溢出。
划分算法效率：因为left和right依次从向中间逼近，直到相等跳出循环，所以循环次数就是N次，它的执行时间是O(N)。
了解了划分算法，我们来说说简单地快速排序：
- 先将一个数组进行划分算法，找到一个位置mid。
保证mid之前的元素值都不大于mid位置值，保证mid之后的元素都不小于mid值。那么mid位置的值就是有序的，因为mid前面的值找不到比它大的，mid后面的找不到比它小的。
2.再递归调用自身两次，分别传递mid之前位置的数组，和mid之后位置的数组。
private static void fastSort(int[] arr) {
fastSort(arr, 0, arr.length - 1);
}
private static void fastSort(int[] arr, int left, int right) {
// 跳出递归的条件
if (right - left <= 0) return;
// 使用arr[right]作为关键值
int mid = partition(arr, left, right, arr[right]);
fastSort(arr, left, mid - 1);
fastSort(arr, mid + 1, right);
}
private static int partition(int[] arr, int left, int right, int pivot) {
// 记录下开始时的right位置，它代表了关键值，最后要将这个关键值移动到中间位置。
// 开始时，right没有加一，因为right位置作为关键值，最后要移动到中间位置。
int originRight = right;
left = left - 1;
while (left < right) {
while(left < right && arr[++left] < pivot);
while(left < right && arr[--right] > pivot);
swap(arr, left, right);
}
// right位置的值，一定不小于pivot，和最开始right位置值进行交换。
// 这样才能满足right位置的值不小于right之前位置的值，又不大于right之后位置的值
swap(arr, right, originRight);
return right;
}
我们简单选用arr[right]作为关键值，从partition方法可以看出：
-
先记录right原始位置originRight。
-
再进行划分算法，找出right最小位置，保证right的值一定是不小于pivot值的。
-
将originRight和right值进行交换，交换之后right位置的值就是关键值了，很容易就知道right之前的值不大于关键值，right之后的值不小于关键值，表示right位置的值在数组中是有序的。
-
返回这个right，然后递归调用自身，直到right - left <= 0跳出递归。
注意一下，会不会出现我们在划分算法中说道的那种极端情况呢，元素都比关键值小。肯定不会，因为关键值是数组中元素。所以while(left < right && arr[++left] < pivot)中前面那个判断可以不用写，因为角标不可能越界。
这种实现方式，只是快速排序中最简单的一种方式。但是它对极端情况处理很差。
考虑一个倒序数组，我们选择了最小值当关键值，那么它找出的right值就是第0位置，它把数组分成了0 -- -1，和1 -- arr.length-1这两个大小极度不均衡的数组，这样就太影响快速排序的效率了。
对于快速排序来说，我们希望分割的两个数组是大小是相等的，这样我们可以将它的调用次数下降到(log N)次，而不是N次，这个很好理解，就像二分查找一样。
所以要防止这种极端情况，我们要对关键值的优化进行选择，一种简单的方式就是三项取中法。
三项取中的快速排序：
不再使用最右端的值当关键值，而是取中间位置的值当关键值，防止对倒序
数组，快速排序效率低的问题。
首先我们获取数组的中位关键值方法:
private static int getPivot(int[] arr, int left, int right) {
// 找到left和right中间值mid
int mid = (left + right) / 2;
// 下面三个判断，保证left、mid、right这三个位置的值是有序排列的。
if (arr[left] > arr[mid]) {
swap(arr, left, mid);
}
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
if (arr[mid] > arr[right]) {
swap(arr, mid, right);
}
// 将mid位置的值和right - 1位置交换。因为原来mid位置的值就是我们需要的关键值。
swap(arr, mid, right - 1);
return arr[right - 1];
}
- 计算中间的位置mid。
- 将left、mid、right这三个位置的值进行排序。
- 将mid和right-1位置的值进行交换。
- 最后返回这个中间值，作为我们的关键值。
int mid = (left + right) / 2记住这个公式，它是计算中间位置的公式，二分查找的时候也是用到这个公式。
其实我们并不需要保证left、mid、right三个值都是有序的，但是一定要使mid位置的值是不能大于right位置的值。我们将mid位置和right - 1位置进行交换，那么right - 1位置就是关键值，再调用partition方法时。我们知道right - 1位置的关键值，是不能在循环中比较，和交换位置的，因为在方法最后这个值要与找到的最小rightPtr位置值进行交换，必须保证交换后的这个righttPtr位置的值，不小于righttPtr位置之前的值，不大于righttPtr位置之后的值。
但是这里就有个问题了，因为在partition方法中，不能比较right - 1位置，那么右端就是从right - 2开始自减的，所以它也就比较不到right位置的值，要保证我们划分算法的正确性，那么right位置的值就不能小于关键值，所以这里的right位置的值就不能小于mid位置的值。这里使用三个判断，主要还是找到合适的中位值。
新的划分算法：
private static int optimizePartition(int[] arr, int left, int right, int pivot) {
// 这里注意一下，pivot的值是在right - 1位置的，并且right位置的值是比right - 1大的。
right = right - 1;
int originRight = right;
left = left - 1;
while (left < right) {
while( arr[++left] < pivot);
// 右边的扫描是从right - 2开始的。
while( left < right && arr[--right] > pivot);
swap(arr, left, right);
}
// right位置的值，一定不小于pivot，和最开始right位置值进行交换。
// 这样才能满足right位置的值不小于right之前位置的值，又不大于right之后位置的值
swap(arr, right, originRight);
return right;
}
还有一点，因为我们要取中位值，那么要求数组长度应该大于3，小于等于3长度的数组，进行特殊处理。
// 手动排序
private static void manualSort(int[] arr, int left, int right) {
int size = right - left + 1;
if (size <= 1)
return;
if (size == 2){
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
return;
}
// 以下是size==3情况
int mid = right - 1;
if (arr[left] > arr[mid]) {
swap(arr, left, mid);
}
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
if (arr[mid] > arr[right]) {
swap(arr,mid, right);
}
}
总的调用方式
// 优化的快速排序
private static void optimizeFastSort(int[] arr) {
optimizeFastSort(arr, 0, arr.length - 1);
}
private static void optimizeFastSort(int[] arr, int left, int right) {
int size = right - left + 1;
if (size <= 3) { // 等于3的数组，手动排序
manualSort(arr, left, right);
} else {
// 得到中位的关键值
int pivot = getPivot(arr, left, right);
int mid = optimizePartition(arr, left, right, pivot);
optimizeFastSort(arr, left, mid - 1);
optimizeFastSort(arr, mid + 1, right);
}
}
快速排序是常用排序中，速度最快的，执行时间是O(N * log N)级。
六.堆排序
先来说说堆：
- 它是一个完全二叉树，即除了最后一层节点不是满的，其他层节点都是满的，即左右节点都有。
- 它不是二叉搜索树，即左节点的值都比父节点值小，右节点的值都不比父节点值小，这样查找的时候，就可以通过二分的方式，效率是(log N)。
- 它是特殊的二叉树，它要求父节点的值不能小于子节点的值。这样保证大的值在上面，小的值在下面。所以堆遍历和查找都是低效的，因为我们只知道
从根节点到子叶节点的每条路径都是降序的，但是各个路径之间都是没有联系的，查找一个值时，你不知道应该从左节点查找还是从右节点开始查找。 - 它可以实现快速的插入和删除，效率都在(log N)左右。所以它可以实现优先级队列。
我们知道栈是先进后出的，普通队列是先进先出的。 而优先级队列会将插入队列中的数据进行排序，然后从大到小取出或者从小到大取出。因此堆就可以容易实现优先级队列，而且效率比较高。
堆是一个二叉树，但是它最简单的方式是通过数组去实现二叉树，而且因为堆是一个完全二叉树，就不存在数组空间的浪费。怎么使用数组来存储二叉树呢？
就是用数组的下标来模拟二叉树的各个节点,比如说根节点就是0，第一层的左节点是1，右节点是2。由此我们可以得出下列公式：
// 对于n位置的节点来说：
int left = 2 * n + 1; // 左子节点
int right = 2 * n + 2; // 右子节点
int parent = (n - 1) / 2; // 父节点，当然n要大于0，根节点是没有父节点的
对于堆来说，只有两个操作，插入insert和删除remove，不管插入还是删除保证堆的成立条件，1.是完全二叉树，2.父节点的值不能小于子节点的值。
public void insert(int value) {
// 第一步将插入的值，直接放在最后一个位置。并将长度加一
store[size++] = value;
// 得到新插入值所在位置。
int index = size - 1;
while(index > 0) {
// 它的父节点位置坐标
int parentIndex = (index - 1) / 2;
// 如果父节点的值小于子节点的值，你不满足堆的条件，那么就交换值
if (store[index] > store[parentIndex]) {
swap(store, index, parentIndex);
index = parentIndex;
} else {
// 否则表示这条路径上的值已经满足降序，跳出循环
break;
}
}
}
主要步骤:
- 直接将value插入到size位置，并将size自增，这样store数组中插入一个值了。
- 要保证从这个叶节点到根节点这条路径上的节点，满足父节点的值不能小于子节点。
- 通过int parentIndex = (index - 1) / 2得到父节点，如果比父节点值大，那么两者位置的值交换，然后再拿这个父节点和它的父父节点比较。
直到这个节点值比父节点值小，或者这个节点已经是根节点就退出循环。
因为我们每次只插入一个值，所以只需要保证新插入位置的叶节点到根节点路径满足堆的条件，因为其他路径没做操作，肯定是满足条件的。第二因为是直接在size位置插入值，所以肯定满足是完全二叉树这个条件。因为每次循环index都是除以2这种倍数递减的方式，所以它最多循环次数是(log N)次。
public int remove() {
// 将根的值记录，最后返回
int result = store[0];
// 将最后位置的值放到根节点位置
store[0] = store[--size];
int index = 0;
// 通过循环，保证父节点的值不能小于子节点。
while(true) {
int leftIndex = 2 * index + 1; // 左子节点
int rightIndex = 2 * index + 2; // 右子节点
// leftIndex >= size 表示这个子节点还没有值。
if (leftIndex >= size) break;
int maxIndex = leftIndex;
if (store[leftIndex] < store[rightIndex]) maxIndex = rightIndex;
if (store[index] < store[maxIndex]) {
swap(store, index, maxIndex);
index = maxIndex;
} else {
break;
}
}
return result;
}
在堆中最大值就在根节点，所以操作步骤：
- 将根节点的值保存到result中。
- 将最后节点的值移动到根节点，再将长度减一，这样满足堆成立第一个条件，堆是一个完全二叉树。
- 使用循环，来满足堆成立的第二个条件，父节点的值不能小于子节点的值。
- 最后返回result。
那么怎么样满足堆的第二个条件呢？
因为根节点的值现在是新值，那么就有可能比它的子节点小，所以就有可能要进行交换。
- 我们要找出左子节点和右子节点那个值更大，因为这个值可能要和父节点值进行交换，如果它不是较大值的话，它和父节点进行交换之后，就会出现父节点的值小于子节点。
- 将找到的较大子节点值和父节点值进行比较。
- 如果父节点的值小于它，那么将父节点和较大子节点值进行交换，然后再比较较大子节点和它的子节点。
- 如果父节点的值不小于子节点较大值，或者没有子节点(即这个节点已经是叶节点了)，就跳出循环。
- 每次循环我们都是以2的倍数递增，所以它也是最多循环次数是(log N)次。
所以通过堆这种方式可以快速实现优先级队列，它的插入和删除操作的效率都是O(log N)。
那么怎么实现堆排序？这个很简单，利用优先队列的特性：
- 先遍历数组。将数组中的值依次插入到堆中。
- 然后再用一个循环将值从堆中取出来。
private static void headSort(int[] arr) {
int size = arr.length;
Head head = new Head(size);
for (int i = 0; i < size; i++) {
head.insert(arr[i]);
}
for (int i = 0; i < size; i++) {
// 实现从大到小的排序
arr[size - 1 - i] = head.remove();
}
}
堆排序的效率：因为每次插入数据效率是O(log N)，而我们需要进行n次循环，将数组中每个值插入到堆中，所以它的执行时间是O(N * log N)级。
最后附上整个排序的源码：
package suanfa_4.one;
import java.util.Random;
public class SortTest {
// 冒泡排序
private static void bubbleSort(int[] arr) {
int size = arr.length;
// 外层循环，保证out之后的值 是按照从小到大顺序排列的。
for (int out = size - 1; out > 1; out --) {
// 内层循环，将最大的值移动到最后out位置，实现了大数冒泡
for (int in = 0; in < out; in++) {
if (arr[in] > arr[in + 1]) {
swap(arr, in, in + 1);
}
}
}
}
// 选择排序
private static void selectSort(int[] arr) {
int size = arr.length;
// 外层循环，保证out之前的都是有序的
for(int out = 0; out < size; out ++) {
int mixIndex = out;
// 内层循环，找到out位置最小值
for (int in = out + 1; in < size; in++) {
if (arr[mixIndex] > arr[in]) {
mixIndex = in;
}
}
if (mixIndex != out) {
swap(arr, mixIndex, out);
}
}
}
// 插入排序
private static void insertSort(int[] arr) {
int size = arr.length;
// out之前的是有序的，所以第0位置是有序的，然后将后面的数据插入到这个有序数组对应位置
for(int out = 1; out < size; out++) {
// 记录下out位置的值，将它替换至正确的位置
int temp = arr[out];
int in = out;
// arr[in - 1] <= temp 表示temp就应该插入in位置，因为temp比in-1位置的值大，又比in+1位置的值小
while(in - 1 >= 0 && arr[in - 1] > temp) {
arr[in] = arr[in - 1];
in --;
}
if (in != out) arr[in] = temp;
}
}
private static void shellSort(int[] arr) {
int size = arr.length;
int h = 1;
while(h <= size / 3) {
// 这里加1是保证h = (h - 1) / 3最后一个值是1，
h = h * 3 + 1;
}
while (h > 0) {
for(int out = h; out < size; out++) {
int temp = arr[out];
int in = out;
// arr[in - h] <= temp 表示temp就应该插入in位置，因为temp比in-h位置的值大，又比in+h位置的值小
while(in - h >= 0 && arr[in - h] > temp) {
arr[in] = arr[in - h];
in = in - h;
}
if (in != out) arr[in] = temp;
}
h = (h - 1) / 3;
}
}
private static void headSort(int[] arr) {
int size = arr.length;
Head head = new Head(size);
for (int i = 0; i < size; i++) {
head.insert(arr[i]);
}
for (int i = 0; i < size; i++) {
// 实现从大到小的排序
arr[size - 1 - i] = head.remove();
}
}
static class Head{
private int[] store;
private int size;
public Head(int size) {
this.store = new int[size];
}
public void insert(int value) {
// 第一步将插入的值，直接放在最后一个位置。并将长度加一
store[size++] = value;
// 得到新插入值所在位置。
int index = size - 1;
while(index > 0) {
// 它的父节点位置坐标
int parentIndex = (index - 1) / 2;
// 如果父节点的值小于子节点的值，你不满足堆的条件，那么就交换值
if (store[index] > store[parentIndex]) {
swap(store, index, parentIndex);
index = parentIndex;
} else {
// 否则表示这条路径上的值已经满足降序，跳出循环
break;
}
}
}
public int remove() {
// 将根的值记录，最后返回
int result = store[0];
// 将最后位置的值放到根节点位置
store[0] = store[--size];
int index = 0;
// 通过循环，保证父节点的值不能小于子节点。
while(true) {
int leftIndex = 2 * index + 1; // 左子节点
int rightIndex = 2 * index + 2; // 右子节点
// leftIndex >= size 表示这个子节点还没有值。
if (leftIndex >= size) break;
int maxIndex = leftIndex;
if (store[leftIndex] < store[rightIndex]) maxIndex = rightIndex;
if (store[index] < store[maxIndex]) {
swap(store, index, maxIndex);
index = maxIndex;
} else {
break;
}
}
return result;
}
}
private static void fastSort(int[] arr) {
fastSort(arr, 0, arr.length - 1);
}
private static void fastSort(int[] arr, int left, int right) {
// 跳出递归的条件
if (right - left <= 0) return;
// 使用arr[right]作为关键值
int mid = partition(arr, left, right, arr[right]);
fastSort(arr, left, mid - 1);
fastSort(arr, mid + 1, right);
}
private static int partition(int[] arr, int left, int right, int pivot) {
// 记录下开始时的right位置，它代表了关键值，最后要将这个关键值移动到中间位置。
// 开始时，right没有加一，因为right位置作为关键值，最后要移动到中间位置。
int originRight = right;
left = left - 1;
while (left < right) {
while(left < right && arr[++left] < pivot);
while(left < right && arr[--right] > pivot);
swap(arr, left, right);
}
// right位置的值，一定不小于pivot，和最开始right位置值进行交换。
// 这样才能满足right位置的值不小于right之前位置的值，又不大于right之后位置的值
swap(arr, right, originRight);
return right;
}
// 优化的快速排序
private static void optimizeFastSort(int[] arr) {
optimizeFastSort(arr, 0, arr.length - 1);
}
private static void optimizeFastSort(int[] arr, int left, int right) {
int size = right - left + 1;
if (size <= 3) { // 等于3的数组，手动排序
manualSort(arr, left, right);
} else {
// 得到中位的关键值
int pivot = getPivot(arr, left, right);
int mid = optimizePartition(arr, left, right, pivot);
optimizeFastSort(arr, left, mid - 1);
optimizeFastSort(arr, mid + 1, right);
}
}
// 手动排序
private static void manualSort(int[] arr, int left, int right) {
int size = right - left + 1;
if (size <= 1)
return;
if (size == 2){
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
return;
}
// 以下是size==3情况
int mid = right - 1;
if (arr[left] > arr[mid]) {
swap(arr, left, mid);
}
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
if (arr[mid] > arr[right]) {
swap(arr,mid, right);
}
}
private static int getPivot(int[] arr, int left, int right) {
// 找到left和right中间值mid
int mid = (left + right) / 2;
// 下面三个判断，保证left、mid、right这三个位置的值是有序排列的。
if (arr[left] > arr[mid]) {
swap(arr, left, mid);
}
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
if (arr[mid] > arr[right]) {
swap(arr, mid, right);
}
// 将mid位置的值和right - 1位置交换。因为原来mid位置的值就是我们需要的关键值。
swap(arr, mid, right - 1);
return arr[right - 1];
}
private static int optimizePartition(int[] arr, int left, int right, int pivot) {
// 这里注意一下，pivot的值是在right - 1位置的，并且right位置的值是比right - 1大的。
right = right - 1;
int originRight = right;
left = left - 1;
while (left < right) {
while( arr[++left] < pivot);
// 右边的扫描是从right - 2开始的。
while( left < right && arr[--right] > pivot);
swap(arr, left, right);
}
// right位置的值，一定不小于pivot，和最开始right位置值进行交换。
// 这样才能满足right位置的值不小于right之前位置的值，又不大于right之后位置的值
swap(arr, right, originRight);
return right;
}
private static void swap(int[] arr, int one, int two) {
int temp = arr[one];
arr[one] = arr[two];
arr[two] = temp;
}
private static int[] getArr(int n) {
Random random = new Random();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(10000);
}
return arr;
}
private static boolean isSort(int[] arr) {
int size = arr.length;
for(int i = 0; i < size - 1; i++){
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
private static void printArr(int[] arr){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < arr.length; i++){
sb.append(arr[i]+",");
}
System.out.println("arr=="+sb.toString());
System.out.println("isSort=="+isSort(arr));
}
private static int partition(int[] arr, int pivot) {
// 将left开始设置为-1，因为下面判断使用arr[++left]，会先自增。
// 如果使用arr[left++]，那么进行判断arr[++left] < pivot时的left值
// 和进行交换swap(arr, left, right)就不是同一个值了。
int left = -1;
// 同left一样，比真实坐标大一的位置
int right = arr.length;
while (left < right) {
while (left < right && arr[++left] < pivot);
while (left < right && arr[--right] > pivot);
swap(arr, left, right);
}
return right;
}
public static void main(String[] args){
int[] arr = getArr(100);
optimizeFastSort(arr);
printArr(arr);
arr = getArr(100);
selectSort(arr);
printArr(arr);
arr = getArr(100);
insertSort(arr);
printArr(arr);
arr = getArr(100);
shellSort(arr);
printArr(arr);
arr = getArr(100);
headSort(arr);
printArr(arr);
arr = getArr(100);
fastSort(arr);
printArr(arr);
// arr = getArr(50);
// partition(arr, 50);
// printArr(arr);
System.out.println();
System.out.println();
System.out.println();
main3();
}
private static void main3() {
int count = 10000*10;
int[] arr = getArr(count);
SpendTime spendTime = new SpendTime();
shellSort(arr);
System.out.println("isSort=="+isSort(arr)+" size=="+arr.length);
System.out.println("花费时间:"+spendTime.getSpendSeconds());
arr = getArr(count);
spendTime = new SpendTime();
fastSort(arr);
System.out.println("isSort=="+isSort(arr)+" size=="+arr.length);
System.out.println("花费时间:"+spendTime.getSpendSeconds());
arr = getArr(count);
spendTime = new SpendTime();
optimizeFastSort(arr);
System.out.println("isSort=="+isSort(arr)+" size=="+arr.length);
System.out.println("花费时间:"+spendTime.getSpendSeconds());
arr = getArr(count);
spendTime = new SpendTime();
headSort(arr);
System.out.println("isSort=="+isSort(arr)+" size=="+arr.length);
System.out.println("花费时间:"+spendTime.getSpendSeconds());
}
}
网友评论