几种简单的排序算法，记录在博客中，主要学习下其中的思想。

冒泡排序

1.   （遍历下标 0 -> i） 将相邻两个元素比较

2. 将较大的放到后面，直到下标为 i ，即表明下标 i 及以后的元素排序完成
   

3. 再次（遍历下标 0 -> i-1）

4. 再次（遍历下标 0 -> i-2）

5. ......

6. 直到剩下最后一个元素

package net.jimmyme;

import java.util.Arrays;

public class BubbleSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        bubbleSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void bubbleSort(){
        
        for (int i = 0; i < source.length; i++) {
            for (int j = 0; j < source.length-1-i; j++) {
                if (source[j] > source[j+1]) {
                    
                    int temp = source[j+1];
                    source[j+1] = source[j];
                    source[j] = temp;
                }
            }
        }
    }

}

选择排序

1. 遍历下标 0 -> n  选出最小的元素（下标为 i）
   

2. 交换 下标为 0 与 i 的元素
   

3. 再次（遍历下标 1 -> n) 选出最小的元素（下标为 i）
   

4. 交换
   

5. ......

6. 直到剩下最后一个元素

package net.jimmyme;

import java.util.Arrays;

public class SelectSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        selectSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void selectSort(){
        
        for (int i = 0; i < source.length; i++) {
            int min = i;
            for (int j = i+1; j < source.length; j++) {
                // find the index of min value 
                if (source[j] < source[min]) {
                    
                    min = j;
                }
            }
            //swap
            int temp = source[i];
            source[i] = source[min];
            source[min] = temp;
            
        }
    }

}

插入排序

1. 第0位元素保持不动，从第一位开始，将选取的元素与已经有序的序列对比
   

2. 找到前面小于等于 该元素  后面大于等于该元素的位置
   

3. 将该元素 插入两者之间
   

4. 直到所有元素都插入

package net.jimmyme;

import java.util.Arrays;

public class InsertSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        insertSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void insertSort(){
        
        for (int i = 1; i < source.length; i++) {
            
            int temp = source[i]; //选中第i个元素
            int j = i-1; // 从第i-1元素开始 往前找 只要比temp大就往后移
            
            while (j >= 0 && source[j] > temp) {
                source[j+1] = source[j];
                j--;
            }
            // 直到找到前面一个比自己小，后一个就是该元素的位置
            source[j+1] = temp;
        }
    }
}

希尔排序

    希尔排序就是插入排序的优化版本，将步长定为 d ，分成 d 个组，每个组进行插入排序，经过一轮之后 逐步缩短步长 d 。直到步长变为1（标准插入排序）

package net.jimmyme;

import java.util.Arrays;

public class ShellSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        shellSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void shellSort(){
        int d = source.length/2;
        
        while (d > 0) {
            // 相当于步长为d的插入排序法，且步长逐渐缩小，当步长为1时 就是标准的插入排序
            for (int i = d; i < source.length; i++) {
                int j = i-d;
                int temp = source[i];
                while (j >= 0 && source[j] > temp) {
                    source[j+d] = source[j];
                    j -= d;
                }
                
                source[j+d] = temp;
            }
            d /= 2;
        }
        
    }
}

推荐您阅读更多有关于“排序算法，Java，”的文章