Java排序问题（二）

4、快速排序

     思想：其实上快排思路很简单。尤其是这种简单的数字排序，就是每次把第一个当做标兵；然后士兵A和士兵B分别从数组两端开始走，如果大于标兵则放在左边，小于2标兵则放在右端，一次递归，出来的就是排序好的数列了（和汉诺塔的思想是有点像的）

 

package Sort;

import java.util.Scanner;

public class quickSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
	 
		System.out.println("快速排序：");
		System.out.println("请输入一个数组长度，可多次输入：");
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				System.out.println("请输入第" + (i + 1) + "个数；");
				arr[i] = sc.nextInt();
			}
			// 快速排序主题
			quickSort sort = new quickSort();
			sort.quickSort(arr, 0, n - 1);
			System.out.println("输出排序后的数组：");
			for (int j = 0; j < n; j++) {
				System.out.print(arr[j] + " ");
			}
			System.out.println();
		}
	}

	// 划分数组
	int partion(int[] arr, int p, int r) {
		int x = arr[r];
		int i = p - 1;// 注意这点，把i设成负值，然后作为移动的标志
		int j;
		for (j = p; j < r; j++) {
			if (arr[j] <= x) {
				i++;
				int temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
		int temp = arr[j];
		arr[j] = arr[i + 1];
		arr[i + 1] = temp;
		return i + 1;// 返回的应该是交换后的哨兵的位置
	}

	// 递归解决每个划分后的小数组
	void quickSort(int[] arr, int p, int r) {
		if (p < r) {
			int q = partion(arr, p, r);
			quickSort(arr, p, q - 1);
			quickSort(arr, q + 1, r);
		}
	}

}

 5、希尔排序

 

     思想：输入一个数组，把这二个数组分成多个小的数组，进行排序，第一次取数组的二分之一t=length/2，然后就是a[t]和a[t-t]进行比较大小，依次增加，一直到a[length-1];第二部是t=t/2重复上一步的步骤，依次递推下去，知道t==1;输出的新数列就是排序好的数列了。

package Sort;

import java.util.Scanner;

public class shellSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		System.out.println("希尔排序：");
		System.out.println("输入一个数组长度，可多次输入：");
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				System.out.println("请输入第" + (i + 1) + "个数；");
				arr[i] = sc.nextInt();
			}
			// 希尔排序主题
			
			//调用shellSort函数
			shellSort ss = new shellSort();
			ss.shellsort(arr);
			System.out.println("排序后：");
			for (int k = 0; k < n; k++) {
				System.out.print(arr[k] + " ");
			}
			System.out.println();
		}
	}
//shellSort函数
	public void shellsort(int[] arr) {
		int temp = 0;
		int j = 0;
		for (int t = arr.length / 2;t > 0; t /= 2) {
			for (int i = t; i < arr.length; i++) {
				temp = arr[i];
				for (j = i; j >=  t; j -= t) { 
					if (temp <arr[j - t]) {
						arr[j] = arr[j - t];
					} else {
						break;
					}
				}
				arr[j] = temp;
			}
		}
	}
/**
 * 6 5 2 3 1 4 0
 * 
 * 
 */
}