交换排序

交换排序的基本思想

根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，也就是说，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序:

比较两个相邻的数，如果前面的数大于后面的数，则将这两个数交换位置。第一次遍历后，最大的数会被放到数组的最后位置，即array[length - 1]。第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要较。

public void bubleSort(int[] arr) {
		for(int i=0;i<arr.length-1;i++) {
			for(int j=0;j<arr.length-1-i;j++) {
				if(arr[j]>arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
			}
		}
	}
}

快速排序

基本思想：

1. 先从数列中取出一个数作为基准数
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
3. 再对左右区间重复第二步，直到各区间只有一个数

public void quickSort(int arr[],int left,int right) {
		if(right>left) {
			int index = getIndex(arr,left,right);
			quickSort(arr,left,index-1);
			quickSort(arr,index+1,right);
		}
	}
	public int getIndex(int[] arr,int left,int right) {
		
		int data = arr[left];
		while(left<right) {
			
			while(left<right&&arr[left]<data) {
				left++;
			}
			arr[right] = arr[left];
			while(left<right&&arr[right]>data) {
				right--;
			}
			arr[left] = arr[right];
		}
		arr[left] = data;
		return left;
	}