排序算法

一、冒泡排序

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

冒泡排序的算法是要将最小的数据项放在数组的最开始，并将最大的数据项放在数组的最后。每次比较为真，便将较小的数据项向前移动，同时将较大的数据项向后移动，外层for循环每执行一次，便有一个最大的数据项移至数组最末端，并且不再处理。
冒泡排序是最简单的一种排序方法，也是最慢的一种排序方法。它的算法复杂度是O(n^2)，比较次数：N*(N-1)/2，交换次数最坏的情况也是：N*(N-1)/2。

二、选择排序

	public static void selectionSort(int[] a) {
		int min, temp;
		for (int i = 0; i < a.length - 1; i++) {
			min = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[min])
					min = j;
			}
			if (i != min) {
				temp = a[i];
				a[i] = a[min];
				a[min] = temp;
			}
		}
	}

选择排序的算法是在每一次的循环中，在 a.length – i +1 个 记录中选取最小的数据项作为数组的第i个记录。
虽然选择排序和冒泡排序执行了相同的比较次数：N*(N-1)/2，但是选择排序将必要的交换次数从O(n^2)减少到了O(n)。对于100个数据项，需要4950次比较，但选择排序只进行了不到100次交换。当N值很 大时，比较的次数是主要的，但是，选择排序无疑更快，因为它进行的交换次数少的多。所以，当N比较小，特别是如果交换的性能消耗比比较的性能消耗大得多时，用选择排序是相当快的。

三、插入排序

	public void inserionSort(int a[]){
		int temp;
		for (int out=1;out < a.length;out++){
			temp = a[out];
			int in = out;
			while (in >0 && a[in-1] >= temp){
				a[in] = a[in-1];
				in--;
			}
			a[in] = temp;
		}
	}

插入排序的算法是将一个数据项插入到已排好序的有序数组(部分有序)中，从而得到一个新的、数据项个数增1的有序数组。
插入排序的比较次数实际上大约是N*(N-1)/4 次。复制的次数大致等于比较的次数，由于一次复制与一次交换的时间耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。
如果数据基本有序，插入排序几乎只需要O(N)的时间；然后对于逆序排列的数据，每次比较和移动都会执行，所以这时插入排序并不比冒泡快。

四、快速排序

	public static void recQuickSort(int a[], int left, int right) {
		if (right - left <= 0)
			return;
		else {
			int partition = partitionIt(a, left, right);
			recQuickSort(a, left, partition - 1); // sort left side
			recQuickSort(a, partition + 1, right); // sort right side
		}
	}
	public static int partitionIt(int a[], int left, int right) {
		int leftPtr = left - 1; 
		int rightPtr = right;
		
		int pivot = a[right];
		while (true) {
			while (a[++leftPtr] < pivot); 
			while (rightPtr > 0 && a[--rightPtr] > pivot); 
			
			if (leftPtr >= rightPtr)
				break;
			else {
				swap(a, leftPtr, rightPtr);
			}
		}
		swap(a, leftPtr, right);
		return leftPtr;
	}
	
	public static void swap(int a[], int dex1, int dex2)
	{
		int temp = a[dex1];
		a[dex1] = a[dex2];
		a[dex2] = temp;
	}

快速排序的算法是取得数组中的某一个值，并按此值将数组分割为两个字数组，递归对字数组按此方法排序。
快速排序算法的性能主要取决于每次对中间值得获取，换言之即为对数组划分的对称性。
快速排序算法在平均情况下的时间复杂度是O(nlogn)。在大多数情况下，该算法的排序是最快的，快速排序也因此而得名。

评论

2 楼 kdboy 2008-07-24  

发现了，交换应在循环之外。已修改，谢谢了。

错误代码：

	public static void selectionSort(int[] a) {
		int min, temp;
		for (int i = 0; i < a.length - 1; i++) {
			min = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[min])
					min = j;
				if (i != min) {
					temp = a[i];
					a[i] = a[min];
					a[min] = temp;
				}
			}
		}
	}

1 楼 yangtao309 2008-07-24  

楼主 selectionSort方法有问题啊 说出结果为：（251325）221355