啊啊啊啊啊啊！大话数据结构终于看到了排序这一章章啦，然而各路排序神仙，真的是看懂了！仅仅是看懂了，所以打算用两天的时间比几个常见的算法写一遍啦，加深一下印象。嘤嘤嘤
参考博客
十大经典排序算法（动图演示
冒泡排序
这个算法我记得是上C语言就接触了，他的思想是，遇到逆序对，就进行交换啊，就这样慢慢的第n个有序，第n-1个有序.......全部有序。 关键点在于如果一次遍历，都没有交换操作的话，那说明已经有序啦，跳出循环。排序完成。
package com.it592.sort;
public class BubbleSort extends Sort {
@Override
public void sort(int nums[]) {
int len = nums.length;
for (int i = 0; i < len; i++){
boolean flag = true;
for (int j = 0; j < len - i -1; j++){
if(nums[j] > nums[j+1]){ // 判断是否逆序，如果逆序，说明还没找到正确的位置，继续后移
nums[j] += nums[j+1];
nums[j+1] = nums[j] - nums[j+1];
nums[j] -= nums[j+1];
flag = false;
}
}
if (flag)
break;
}
}
}
选择排序
选择排序，按照大话数据结构的话说，其实和冒泡排序差不多，但是这两个算法的侧重点不同，冒泡排序每次都进行交换操作，其实有很多交换是没有必要的，毕竟交换也要费点时，选择排序他只是观察，找到适合某个位置的点，然后再进行交换，这就好比炒股票，冒泡排序是看到每次涨了之后，都卖出去，然后降了再买点回来，而选择排序是看到最高点，再抛售，这就省去了中间交易的开销，也就是冒泡排序时候交换的时候开销。
package com.it592.sort;
public class SelectSort extends Sort {
@Override
public void sort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++){
int key = i;
for (int j = i + 1; j < nums.length; j++){ //找到适合i的值。
if (nums[key] > nums[j])
key = j;
}
if(key != i){
nums[i] += nums[key]; //让i变为有序的
nums[key] = nums[i] - nums[key];
nums[i] -= nums[key];
}
}
}
}
插入排序
插入排序的思想是，假设序列已经有序了，那么我们只需要把当前元素插入到正确的位置即可。首先，对于第一个元素，因为只有一个元素，所以他是有序的，对于第二个元素，则与第一个元素进行判断，如果比第一个元素小，则插到第一个元素之前，第一个元素后移；对于第三个元素，则和前两个元素进行比较，找到合适的位置，插入即可。依次类推，最终有序。
package com.it592.sort;
public class InsertSort extends Sort {
@Override
public void sort(int[] nums) {
int len = nums.length;
for(int i = 0; i < len -1 ; i++){
int tmp = nums[i+1];
int j = i+1;
for(; j > 0; j--){
if(nums[j-1] > tmp){
nums[j] = nums[j-1];
}else
break;
}
nums[j] = tmp;
}
}
}
希尔排序
在插入排序中，由于要把某个元素放到合适的位置上，这样可能就会导致其他元素偏离他本来的位置很远，希尔排序是对插入排序的一种改进，他可以将小的元素放到前面去，而大的元素集中在尾部。方法是，将数组进行分组，例如[2,5,1,4,5,55,11,1,15,19,2,33,55,8]，我们设置space=3，那么则[2,11,19,55]，[5,5,1,2,8],[1,55,15,33]为三个分组，使用插入排序对他们进行排序后，就会得到以下结果[2,1,1,11,2,15,19,5,33,55,5,55,8]，通过这样一轮排序之后，就会发现小的部分相对集中在前面，而大数则集中在后面。最终循环完毕，有序
package com.it592.sort;
public class ShellSort extends Sort {
@Override
public void sort(int[] nums) {
int gap = nums.length / 3 + 1;
while (true){
for (int i = 0; i < nums.length - gap; i += gap){
int tmp = nums[i+gap];
int j = i + gap;
for (; j > 0; j -= gap){
if(nums[j-gap] > tmp)
nums[j] = nums[j-gap];
else
break;
}
nums[j] = tmp;
}
if (gap == 1) // gap 等于 1的时候，说明进行了一次正常的插入排序，over，推出。
break;
gap = gap / 3 + 1;
}
}
}
归并排序
归并排序，其实就是相当于划分成子问题，然后再合并起来，这玩意难点不在思路，递归实现贼方便，但是嘤嘤嘤，非递归就不那么容易啦。具体代码解释吧
package com.it592.sort;
public class MergeSort extends Sort {
@Override
public void sort(int[] nums) {
mergeSort(nums);
}
private void mergeSort(int[] nums){
/*
主要包含两个部分，第一个分组，第二个是组内排序并合并
*/
int space = 2; //space 用来设置当前划分的子问题的大小*2，
while (space <= nums.length){
int i = 0;
while (i + space <= nums.length){
merge(nums,i,i + space / 2, i + space ); // 将子问题的解合并
i += space; //更新子问题的坐标，向后移动，继续解决其他子问题
}
if ((i + space / 2 - 1) < nums.length) //如果有剩余的没办法进行排序，那此次进行排序。
merge(nums, i, i+space/2, nums.length);
space *= 2;
}
merge(nums, 0, space / 2, nums.length); //从头到尾，合并一次。
}
private void merge(int nums[],int left, int center, int right){
int temp[] = new int[right - left + 1];
int cnt = 0;
int i = left;
int j = center;
while (i < center && j < right){
if (nums[i] > nums[j]){
temp[cnt++] = nums[j++];
}else
temp[cnt++] = nums[i++];
}
while (i < center){
temp[cnt++] = nums[i++];
}
while (j < right){
temp[cnt++] = nums[j++];
}
cnt = 0;
for (i = left; i < right; i++){
nums[i] = temp[cnt++];
}
}
}
快速排序
快速排序的思想主要也是分治，主要是找到一个节点，把他放到合适的位置上，使左边的都比节点小(大)，右边都比节点大(小)。他最关键的点就在找这个节点的合适位置，找法就是从右到左找到比节点小的点，交换，然后再从左往右找到合适的点，交换，直接i和j相等.具体看参考。
白话经典算法系列之六 快速排序 快速搞定
package com.it592.sort;
public class QuickSort extends Sort {
@Override
public void sort(int[] nums) {
quick_sort(nums,0,nums.length-1);
}
private void quick_sort(int[] nums, int left, int right){
int i = left;
int j = right;
if(left < right){
int tmp = nums[i];
while (i < j){
while (i < j && nums[j] > tmp)
j--; // 找到第一个小数
if(i < j)
nums[i++] = nums[j];
while (i < j && nums[i] < tmp)
i++;
if(i < j)
nums[j--] = nums[i];
}
nums[i] = tmp;
quick_sort(nums,left,i-1);
quick_sort(nums,i+1,right);
}
}
}