常见排序及源码

一、冒泡排序

public class BubbleSort {
    public static void BubbleSort(int[] arr) {
        int temp;//定义一个临时变量
        for(int i=0;i<arr.length-1;i++){//冒泡趟数
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j+1]<arr[j]){
                    temp = arr[j]; //将第一个数组暂存到temp
                    arr[j] = arr[j+1];//因为arr[j+1]比arr[j]值小，所以将arr[j+1]放到arr[j]之前，即交换位置
                    arr[j+1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int arr[] = new int[]{1,6,2,2,5};
        BubbleSort.BubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

二、选择排序

public class SelectionSort {
	public static void main(String[] args) {
		int[] arr = { 5, 2, 8, 4, 9, 1 };
		System.out.println("交换之前：");
		for (int num : arr) {
			System.out.print(num + " ");
		}
		// 选择排序的优化
		for (int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
			int k = i;
			for (int j = k + 1; j < arr.length; j++) {// 选最小的记录
				if (arr[j] < arr[k]) {
					k = j; // 记下目前找到的最小值所在的位置
				}
			}
			// 在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
			if (i != k) { // 交换a[i]和a[k]
				int temp = arr[i];
				arr[i] = arr[k];
				arr[k] = temp;
			}
		}
		System.out.println();
		System.out.println("交换后：");
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}

}

第一次排序： 最小数据1，把1放在首位，也就是1和5互换位置，

                           排序结果：1  2  8  4  9  5

第二次排序：第1以外的数据{2  8  4  9  5}进行比较，2最小，

                           排序结果：1  2  8  4  9  5

第三次排序：除1、2以外的数据{8  4  9  5}进行比较，4最小，8和4交换

                           排序结果：1  2  4  8  9  5

第四次排序：除第1、2、4以外的其他数据{8  9  5}进行比较，5最小，8和5交换

                           排序结果：1  2  4  5  9  8

第五次排序：除第1、2、4、5以外的其他数据{9  8}进行比较，8最小，8和9交换

                           排序结果：1  2  4  5  8  9

 

三、 直接插入排序

public class DirectInsertSort {
	public static void main(String[] args) {
		int[] arr = { 11, 25, 45, 26, 12, 78 };
		sort(arr);
	}

	public static void sort(int[] arr) {
		int tmp;
		for (int i = 1; i < arr.length; i++) {
			// 待插入数据
			tmp = arr[i];
			int j;
			for (j = i - 1; j >= 0; j--) {
				if (arr[j] > tmp) {	// 判断是否大于tmp，大于则后移一位
					arr[j + 1] = arr[j];
				} else {
					break;
				}
			}
			arr[j + 1] = tmp;
			System.out.println(i + ":" + Arrays.toString(arr));
		}
	}
}

1、首先比较25和11的大小，11小，位置互换，

       第一轮排序后，顺序为：[11, 25, 45, 26, 12, 78]。

2、对于第三个数据45，其大于11、25，所以位置不变，

       顺序依旧为：[11, 25, 45, 26, 12, 78]。

3、对于第四个数据26，其大于11、25，小于45，所以将其插入25和45之间，

        顺序为：[11, 25, 26, 45, 12, 78]。

....

4、最终顺序为：[11, 12, 25, 26, 45, 78]。

 

四、 希尔排序

public class ShellSort {
	public static void main(String[] args) {
		int[] arr = { 82, 31, 29, 71, 72, 42, 64, 5, 110 };
		sort(arr);
	}

	public static void sort(int[] arrays) {
		if (arrays == null || arrays.length <= 1) {
			return;
		}
		// 增量
		int incrementNum = arrays.length / 2;
		while (incrementNum >= 1) {
			for (int i = 0; i < arrays.length; i++) {
				// 进行插入排序
   				for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {
					if (arrays[j] > arrays[j + incrementNum]) {
						int temple = arrays[j];
						arrays[j] = arrays[j + incrementNum];
						arrays[j + incrementNum] = temple;
					}
				}
			}
			// 设置新的增量
			incrementNum = incrementNum / 2;
			for (int num : arrays) {
				System.out.print(num + " ");
			}
			System.out.println("");
		}
	}
}

1，第一次取增量设置为array.length/2 = 4    先从82开始以4为增量遍历直到末尾，得到（82,42）

       排序得到{42 ,31 ,29 ,71, 72, 82, 64, 5,110}。

2， 然后从第二个数31开始重复上一个步骤，得到（31,64）

        排序得到{42 ,31 ,29 ,71, 72, 82, 64, 5,110}

       .......

3，以4为增量的遍历完数组之后，

      排序得到{42 ,31,5,71,72,82,64,29,110}