面试时复习的几个排序算法_JAVA_编程开发_程序员俱乐部

class="java">
package com.sort.test;

public class BubbleSortTest {
	public static void main(String[] args) {
		int[] data5 = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		print(data5);
		bubbleSort(data5);
		System.out.println("排序后的数组：");
		print(data5);
	}

	public static void swap(int[] data, int i, int j) {
		if (i == j) {
			return;
		}
		data[i] = data[i] + data[j];
		data[j] = data[i] - data[j];
		data[i] = data[i] - data[j];
	}

	public static void bubbleSort(int[] data) {
		for (int i = 0; i < data.length - 1; i++) {
			// 记录某趟是否发生交换，若为false表示数组已处于有序状态
			boolean isSorted = false;
			for (int j = 0; j < data.length - i - 1; j++) {
				if (data[j] > data[j + 1]) {
					swap(data, j, j + 1);
					isSorted = true;
					print(data);
				}
			}
			if (!isSorted) {
				// 若数组已处于有序状态，结束循环
				break;
			}
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}

package com.sort.test;


public class QuickSortTest {

	private static int partition(int[] data, int i, int j) {
		int pivot = data[i];
		while (i < j) {
			while (i < j && data[j] >= pivot) 
				--j;
			data[i] = data[j];
			while (i < j && data[i] <= pivot) 
				++i;
			data[j] = data[i];
		}
		data[i] = pivot;
		
		return i;
	}
	
	public static void quickSort(int[] data, int i, int j) {
		if (i < j) {
			int pivotLoc = partition(data, i, j);
			quickSort(data, i, pivotLoc - 1);
			quickSort(data, pivotLoc + 1, j);
		}
	}
	
	public static void main(String[] args) {
		int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		print(data);
		quickSort(data, 0, data.length - 1);
		System.out.println("排序后的数组：");
		print(data);

	}
	
	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}

package com.sort.test;

/**
 * 选择排序
 * @author Administrator
 *
 */
public class SelectSortTest {

	public static void main(String[] args) {
		int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		print(data);
		selectSort(data);
		print(data);
	}
	
	public static void swap(int[] data, int i,int j) {
		if (i == j) {
			return;
		}
		data[i] = data[i] + data[j];
		data[j] = data[i] - data[j];
		data[i] = data[i] - data[j];
	}
	
	public static void selectSort(int[] data) {
		for (int i = 0; i < data.length - 1; i++) {
			int minIndex = i;//记录最小值的索引
			for (int j = i + 1; j < data.length; j++) {
				if (data[j] < data[minIndex]) {
					minIndex = j;
				}
			}
			
			if (minIndex != i) {
				swap(data, i, minIndex);
				print(data);
			}
		}
	}
	
	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}