快速排序思想及其算法实现

                           快速排序思想及其算法实现

 

 

快速排序（Quicksort）是对冒泡排序的一种改进。O(N*logN)的算法复杂度使它得到了广泛的应用。

算法的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中的一部分的所有数据都比另一部分都要小，然后按此方法分别对这两部分再分别进行快速排序，这呢哥哥排序过程可以递归处理。

<!--EndFragment-->

以此达到整个数据变成有序序列。

 

算法的过程为：

1.制定杻轴（一般是第一个元素）

2.通过一趟排序将一杻轴为中心，把待排记录分割成独立的两部分，使得左边的记录的关键字小于杻轴值，右边的记录大于杻轴值

3.对左右两部分记录序列重复上述过程，以此类推，直到子序列中只剩下一个记录或不含记录为止

 

 

对于

数据：25   21   65   2   35   7   5   43  

 

第一趟排序的结果：5   21   7   2   25     35   65   43  

第二趟排序的结果：2   5   7   21   25   35   65   43 

第三趟排序的结果：2   5   7   21   25   35   65   43 

第四趟排序的结果：2   5   7   21   25   35   65   4

第五趟排序的结果：2   5   7   21   25   35   43   65

第六趟排序的结果：2   5   7   21   25   35   43   65

 

 

 

代码：

/**
	 * 快速排序
	 * 
	 * @param args
	 */

	public void quickSort(int a[], int left, int right) {
		int q;
		if (left < right) {

			q = partition(a, left, right);
			quickSort(a, left, q - 1);
			quickSort(a, q + 1, right);
			
			
		}

	}

	private int partition(int[] a, int left, int right) {
		int s;

		s = a[left];
	
		while (left <right){

			//向左判断
			while (a[right] > s) {
				right--;
			}
			if(left<right){
				int temp = a[left];				
				a[left] = a[right];
				a[right] = temp;
				left++;
			}
			
			//向右判断
			while (a[left] < s) {
				left++;
			}
			//交换
			if(left<right){
				int temp = a[left];				
				a[left] = a[right];
				a[right] = temp;
				right--;
			}			
			 
		
		}
		//打印数组
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "   ");		
		}
		System.out.println();


		return left;
	}