使用JAVA编写的排序算法

使用java练习的排序算法，逐渐补齐。

---

排序

import java.util.Arrays;

• 选择排序

public class classSort {
	
	public static void selectSort(int[] arr) {
		
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = i+1; j < arr.length; j++) {
				// 用i的下一个元素和它比较
				if (arr[i]>arr[j]) {
					// 交换值
					arr[i]=arr[j]+arr[i]-(arr[j]=arr[i]);
				}
			}
		}
	}

• 冒泡排序

public static void bubbleSort(int[] arr) {
	
	for (int i = 0; i < arr.length-1 ; i++) {
		// 防止越界
		for (int j = 0; j < arr.length-i-1; j++) {
			if (arr[j] > arr[j+1]) {
				/*arr[j] = arr[j] ^ arr[j+1];
				arr[j+1] =arr[j] ^ arr[j+1];
				arr[j] = arr[j] ^ arr[j+1];*/
				arr[j]=arr[j]+arr[j+1]-(arr[j+1]=arr[j]);
			}
		}
	}
}

• 合并排序

// 合并排序（递归）
public void mergeSort(int[] arr,int left,int right){
	
	if (left<right) {
		int mid = (left+right)/2;
		mergeSort(arr, left, mid);
		mergeSort(arr, mid+1, right);
		merge(arr,left,mid,right); // 合并后给arr
	}
}

// merge的写法
public void merge(int[] arr,int left,int mid,int right) {
	//int[] temp = new int[arr.length]; // 暂时存放
	int length = right-left+1;
	int temp[]=new int[length];
	int i = left,
		j = mid+1,
		k = 0;
	while ((i <= mid)&&(j <= right)) {
		if (arr[i]<arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];
		}
	}
	while (i<=mid) {
		temp[k++]=arr[i++];
	}
	while (j<=right) {
		temp[k++]=arr[j++];
	}
	int n=0;
	for(int t=left;t<=right;t++,n++){
           arr[t]=temp[n];
       }
	//System.out.println(Arrays.toString(temp));
	//arr = Arrays.copyOf(temp, temp.length);
	System.out.println(Arrays.toString(arr));
}

• 快速排序

	// 快速排序，分开写
	public static void quickSort(int[] arr,int left,int right){// 分治策略
		if (left<right) {
			int i = AdjustArray(arr,left,right);
			quickSort(arr, left, i-1);
			quickSort(arr, i+1, right);
		}
	}
	
	public static int AdjustArray(int[] arr,int left, int right) {
		int i = left,j=right;
		int x = arr[left];
		while (i<j) {
			while (i<j&&arr[j]>=x)
				j--;
			
			if (i<j) 
				arr[i++]=arr[j];
			
			while (i<j&&arr[i]<x)
				i++;
			
			if (i<j)
				arr[j--]=arr[i];
		}
		arr[i]=x;
		return i;// 返回基准数位置
	}
	
	// 快速排序，合并写
	public void quickSort2(int[] arr,int left,int right) {
		if (left<right) {
			// 可使用中间数做基准
			int i = left,j=right,x=arr[left];
			while (i<j){
				while (i<j&&arr[j]>=x)
					j--;
				
				if(i<j)
					arr[i++] =arr[j];
				
				while (i<j&&arr[i]<x)
					i++;
				
				if(i<j)
					arr[j--] = arr[i];
			}
			arr[i]=x;
			quickSort2(arr, left, i-1);
			quickSort2(arr, i+1, right);
		}
	}

	public static void main(String[] args) {
		
		int[] arrTest = {2,5,1,9,3,7,4,6,8};
		classSort m = new classSort();
		m.quickSort2(arrTest,0,arrTest.length-1);
		System.out.println(Arrays.toString(arrTest));
	}

}