冒泡排序

每次冒泡过程都是数列的第一个元素开始，然后依次和剩余的元素进行比较，若小于相邻的元素，就置换位置，同时会将较大元素作为基准元素，继续与相邻的元素比较，直到最后一个数列元素

代码

public class BubbleSort {

	public static void main(String[] args) {
		int[] a = {9,3,1,4,6,8,7,5,2,12,45,31};
		sort(a);
		print(a);
	}
	static void sort(int[] a) {
		for(int i=a.length-1;i>0;i--) {
		for(int j= 0;j<i;j++) {
			if(a[j]>a[j+1]) swap(a, j, j+1);
		}
		}
	}

	static void swap(int[] a,int i,int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] =temp;
	}
	static void print(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i] + " ");
		}
	}
}

Java快速排序

一、基本思想

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

二、步骤

（1）在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准，称为基准记录；
（2）定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”，key 表示“基准值”；
（3）首先，尾索引向前扫描，直到找到比基准值小的记录(left != righ)，并替换首索引对应的值；
（4）然后，首索引向后扫描，直到找到比基准值大于的记录(left != righ)，并替换尾索引对应的值；
（5）若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束;将基准值(key)替换首索引对应的值;
（6）再进行下一趟排序时，待排序列被分成两个区:[0,left-1],[righ+1,end]
（7）对每一个分区重复步骤2~6，直到所有分区中的记录都有序，排序成功。

三、图解

四、快排代码

/**
 * 快速排序演示
 * @author ws
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};

        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }

    /**
     * @param arr        待排序列
     * @param leftIndex  待排序列起始位置
     * @param rightIndex 待排序列结束位置
     */
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[left];
        //从左右两边交替扫描，直到left = right
        while (left < right) {
            while (right > left && arr[right] >= key) {
                //从右往左扫描，找到第一个比基准值小的元素
                right--;
            }
            //找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) {
                //从左往右扫描，找到第一个比基准值大的元素
                left++;
            }
            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        //基准值归位
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }
}

插入排序

排序过程

直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。对于给定的一组记录，初始时假定第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直到最后一个记录插到有序序列中为止。

示例

以数组{38,65,97,76,13,27,49}为例，

代码实现



public class InsertionSort {

	public static void main(String[] args) {
		int[] a = {38,65,97,76,13,27,49};
		sort(a);
		print(a);
	}
	
	static void sort(int[] a) {
		for(int i = 1; i < a.length; i++) {
			for(int j = i;j>0;j--) {
				if(a[j]<a[j-1]) {
					swap(a, j, j-1);
				}
			}
		}
	}
	
	
	static void swap (int[] a,int i,int j) {
		int temp =a[i];
		a[i] =a[j];
		a[j] = temp;
	}
	static void print(int[] arr) {
		for(int i = 0;i< arr.length;i++) {
			System.out.print(arr[i] +" ");
		}
	}

}

结果

希尔排序

排序过程

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）

代码分析

public class Shell
{
	public static void main(String[] args)
	{
		int[] ins = {2,3,5,1,23,6,78,34,23,4,5,78,34,65,32,65,76,32,76,1,9};
		int[] ins2 = sort(ins);
		for(int in: ins2){
			System.out.println(in);
		}
	}
	public static int[] sort(int[] ins){
		
		int n = ins.length;
		int gap = n/2;
		while(gap > 0){
			for(int j = gap; j < n; j++){
				int i=j;
				while(i >= gap && ins[i-gap] > ins[i]){
					int temp = ins[i-gap]+ins[i];
					ins[i-gap] = temp-ins[i-gap];
					ins[i] = temp-ins[i-gap];
					i -= gap;
				}
			}
			gap = gap/2;
		}
		return ins;
	}
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/115363.html