初级排序算法-选择排序、插入排序、希尔排序

选择排序

选择排序思想
1、假设第一个元素是最小元素,依次从后面的元素中一直到N位置,找到一个最小的元素记录下来,执行一次交换(与最小的元素)
2、然后开始找第二小的元素,重复第一步(以第二个元素为最小元素,依次从向后找,直到到达N位置)。

public void selectionSort(int[] a){
	int length = a.length;
	for(int i = 0; i < length; i++){
		int min = i;
		for(int j = i+1; j < length; j++){
			if(a[min]>a[j]){
				min = j;
			}
		}
		//将找到的最小值与i位置互换
		if(i != min){
			int temp = a[min];
			a[min] = a[i];
			a[i] = a[min];
		}
	}
}

插入排序

插入排序的思想:
先以第一个元素为初始插入第二个元素,组成一个临时数组,然后用插入的元素,与已经有的数组元素依次比较(有序的数组),找到合适位置执行交换。得到一个有序数组。然后插入第三个元素,依次类推。
在这里插入图片描述

public void selectionSort(int[] a){
	int length = a.length;
	for(int i = 1; i < length; i++){
		for(int j = i; j > 0 && a[j] < a[j-1]; j--){
			int temp = a[j];
			a[j] = a[j-1];
			a[j-1] = a[j];
		}
	}
}

希尔排序

思想 : 将数组分成h个小数组,然后插入排序,完成以后,在减小h的值,在进行插入排序。依次类推直到h=1
如: 6 5 4 3 2 1
先分成 h=4个,4小数组依次是 [6,2] 、[5,1] 、[4] 、[3]
然后进行依次进行插入排序得到 2 1 4 3 6 5

最后 h=1,进行插入排序得到 1 2 3 4 5 6
上面的例子不太好,请看下图
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

    public static void sort(int[] a){
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1;

        while (h >=1){
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && a[j]<a[j-h] ; j-=h) {
					int temp = a[j];
					a[j] = a[j-h];
					a[j-h] = a[j];
                }
                h = h / 3;
            }
        }
    }

h可以自己定义规则,并不一定如上面代码所示

总结

选择排序、插入排序、希尔排序 都是属于数量级较小集时使用的排序。 根据测试结果比较,如果数据集大小在100以内,选择排序要比插入排序快。 如果在1000左右,插入排序要比选择排序快。 其次插入排序适合做部分有序的数据集。 对于逆序数据,选择排序要高很多。
希尔排序是插入排序的一个变种,或者说是优化。但是它的执行步骤规律比较有限,很难用数学知识进行估算。


版权声明:本文为dingshuhong_原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。