用java语言实现七大排序算法

自定义Sort接口

• Sort接口为以下排序算法提供比较大小和元素的位置交换。

public abstract class Sort<T extends Comparable<T>> {

    public abstract void sort(T[] nums);

    protected boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }

    protected void swap(T[] a, int i, int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

1.选择排序

• 找出数组最小的元素放在第一个位置。接着，找出数组中剩余的元素中最小的元素放在第二个位置，直到遍历完这个数组。

public class Selection<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 0; i < N - 1; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(nums[j], nums[min])) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

2.冒泡排序

• 从左往右不断交换逆序的元素，经过一轮循环，最大的元素浮到最后侧，在过程中至少有一个元素的最终位置已经确定好。

public class Bubble<T extends Comparable<T>> extends Sort<T> {

	@Override
	public void sort(T[] nums) {

		int N = nums.length;
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < nums.length - i; j++) {
				if(less(nums[j+1], nums[j]))
					swap(nums, j+1, j);
			}
		}
	}
}

3.插入排序

每次都把当前元素插入左侧已经排好序的数据，直到所有的元素都插入左侧，就完成了对该数组的排序。

public class Insertion<T extends Comparable<T>> extends Sort<T> {
	@Override
	public void sort(T[] nums) {
		// TODO Auto-generated method stub
		int n = nums.length;
		for (int i = 1; i < nums.length; i++) {
			T val = nums[i];
			int j = 0;
			for (j = i - 1; j >= 0; j--) {
				if (less(val, nums[j]))
					nums[j + 1] = nums[j];
				else
					break;
			}
			nums[j + 1] = val;
		}
	}
}

4.希尔排序

• 希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的

public class Shell <T extends Comparable<T>> extends Sort<T> {

	@Override
	public void sort(T[] nums) {
		int N = nums.length;
		int h = 1;

		while (h < N / 3) {
			h = 3 * h + 1; // 1, 4, 13, 40, ...
		}
		while (h >= 1) {
			for (int i = h; i < N; i++) {
				for (int j = i; j >= h && less(nums[j], nums[j - h]); j = j - h) {
					swap(nums, j, j - h);
				}
			}
			h = h / 3;
		}
	}
}

5.归并排序

• 以下代码使用自顶向下归并排序，使用分治算法实现，把大问题分对半分成两个小问题，时间复杂度一般为O(nlogn)
• merge方法对两个子数组进行归并，通过把原有的数据复制到辅助数据中，对比辅助中的两个子数组依次按顺序排入原有数组。

public class MergeSort<T extends Comparable<T>> extends Sort<T> {

	protected T[] aux;

	public void merge(T[] nums, int l, int m, int h) {
		int i = l, j = m + 1;

		for (int k = l; k <= h; k++) {
			aux[k] = nums[k];
		}

		for (int k = l; k <= h; k++) {
			if (j > h)
				nums[k] = aux[i++];
			else if (i > m)
				nums[k] = aux[j++];
			else if (aux[i].compareTo(aux[j]) <= 0)
				nums[k] = aux[i++];
			else
				nums[k] = aux[j++];
		}
	}
	@Override
	public void sort(T[] nums) {

		aux = (T[]) new Comparable[nums.length];
		sort(nums, 0, nums.length - 1);
	}
	public void sort(T[] nums, int l, int h) {
		if (h <= l)
			return;
		int m = l + (h - l) / 2;
		sort(nums, l, m);
		sort(nums, m + 1, h);
		merge(nums, l, m, h);
	}
}

6.快速排序

• 以切分为基准分成两个子数组，左子数组小于切分元素，右子数组大于切分元素。当两个子数组排好序时整个数组就排好序了。
• partition方法：
  • 取nums[l]为切分元素，从左往右扫描直到找到一个大于它的元素，再从右往左扫描找到一个小于它的元素，交换这两个元素的位置。
  • 不断进行这个过程，直到指针i左侧元素<切分元素，指针j右侧元素大于切分元素。当两个指针相遇时，交换指针i和指针j的位置。

public class QuickSort<T extends Comparable<T>> extends Sort<T> {
	private int partition(T[] nums, int l, int h) {
		int i = l, j = h + 1;
		T v = nums[l];
		while (true) {
			while (less(nums[++i], v) && i != h);
			while (less(v, nums[--j]) && j != l);
			if (i >= j)
				break;
			swap(nums, i, j);
		}
		swap(nums, l, j);
		return j;
	}

	@Override
	public void sort(T[] nums) {
		// TODO Auto-generated method stub
		shuffle(nums);
		sort(nums, 0, nums.length - 1);
	}

	public void sort(T[] nums, int l, int h) {
		if (h <= l)
			return;
		int j = partition(nums, l, h);
		sort(nums, l, j - 1);
		sort(nums, j + 1, h);
	}

	private void shuffle(T[] nums) {
		List<Comparable> list = Arrays.asList(nums);
		Collections.shuffle(list);
		list.toArray(nums);
	}
}

7.堆排序

• sort()：堆的构建，从右往左进行下沉操作。不断用堆顶的元素与数组的最后一个元素交换，同时堆的大小不断减一，直到堆的大小为1，数组就排好序了。

public class HeapSort <T extends Comparable<T>> extends Sort<T> {
	@Override
	public void sort(T[] nums) {
		int N = nums.length - 1;
		for (int k = N / 2; k >= 1; k--) {
			sink(nums,k,N);
		}

		while(N > 1) {
			swap(nums, 1, N--);
			sink(nums,1,N);
		}
	}
	private void sink(T[] nums, int k, int N) {
		while(2 * k  <=  N){
			int j = 2 * k;
			if(j < N && less(nums,j,j+1))
				j++;
			if(!less(nums,k,j))
				break;
			swap(nums, k, j);
			k = j;
		}
	}

	private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}