快速排序

package com.wjy.renren;

import java.util.Arrays;

public class QuickSort {
	public static void main(String args[]){
		int[] array={6,8,4,2,7,9,1,1,9,5};
		System.out.println("QuickSort:  ");
		quickSort(array, 0, array.length-1);
		System.out.println(Arrays.toString(array));
	}
	private static void quickSort(int[] array,int head,int tail){
		int begin=head;
		int end=tail;
		if(begin>=end){
			return;
		}
		int temp=array[begin];
		while(true){
			while(temp<=array[end]&&(begin<end)){
				end--;
			}
			if(begin>=end){
				break;
			}
			array[begin]=array[end];
			while(temp>=array[begin]&&(begin<end)){
				begin++;
			}
			if(begin>=end){
				break;
			}
			array[end]=array[begin];
		}
		array[end]=temp;
		quickSort(array, head, begin-1);
		quickSort(array, end+1, tail);
	}
}

 

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

 

最近发现了一个类似于快排的算法，交换次数很少，和快排思想一样，就是每次确定最后一个元素的最终位置，将小于他的放在左边，大于它的放右边。

int count=0;
void swap(int *arr,int i,int j)
{
	int temp;
	temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;

}

int partion(int *arr,int begin,int end)
{
	int movenum=0;
	int value=arr[end];
	int i;
	int pos=begin;
	for(i=begin;i<end;i++)
	{
		if(value>=arr[i])
		{
			if(pos!=i)
			{
				swap(arr,pos,i);
				count++;
			}
			pos++;
			//movenum++;
		}
	}
	//swap(arr,begin+movenum,end);
	swap(arr,pos,end);
	count++;
	return pos;
}
void compute(int *arr,int begin,int end)
{
	if(arr==NULL || begin<0 || end<0 || begin>=end)
	{
		return;
	}
	else
	{
		int middle=partion(arr,begin,end);
		if(middle>begin)
		{
			compute(arr,begin,middle-1);
		}
		if(middle<end)
		{
			compute(arr,middle+1,end);
		}
	}
}
int main()
{

	int arr[100];
    int n;
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
	}
	compute(arr,0,n-1);
	for(i=0;i<n;i++)
	{
		printf("%d\n",arr[i]);
	}
	printf("count is：%d\n",count);
	system("pause");
	return 0;
}