常用排序算法总结

一、冒泡排序

临近的数字两两进行比较，按照从小到大或者从大到小的顺序交换，这样一趟后，最大或者最小的数字被交换到最后一位。
然后再从头开始两两进行比较交换，直到排序完成。

　　交换数组中两个元素的方法：

public static void swap(int[] arr,int i,int j){
	int swap=arr[i];
	arr[i]=arr[j];
	arr[j]=swap;
}

冒泡排序算法代码实现

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
	for (int j = 0; j < len - i - 1; j++) {
            if (arr[j + 1] < arr[j])
		swap(arr, j + 1, j);
		}
	}
}

二、选择排序

直接从待选择排序数组里面选择一个最小（或者最大）的数字，与第一个位置的数交换。
然后再在剩下的数中选择最小（或者最大）的数字，与第二个位置的数字交换，如此循环到只剩下一个数字为止。

选择排序代码实现：

public static void selectSort(int[] arr) {
	int len = arr.length;
	for (int i = 0; i < len; i++) {
		int min = arr[i];
		int min_index = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[j] < min) {
				min = arr[j];
				min_index = j;
			}
		}
		swap(arr, min_index, i);
	}
}

三、插入排序

　　每一步将一个待排序数据按其大小插入到已经排序的数组中的适当位置，直到全部插入完毕。
　　插入排序代码实现：
　　

public static void insertSort(int[] arr) {
	int len = arr.length;
	int j = 0;
	for (int i = 0; i < len; i++) {
		int temp = arr[i];
		for (j = i; j > 0 && temp < arr[j - 1]; j--) {
			arr[j] = arr[j - 1];
		}
		arr[j] = temp;
	}
}

四、快速排序

选择一个基本元素，通常选择第一个元素或者最后一个元素，通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，另一部分大于或等于基准元素。
这一趟扫描结束后，该基准就处于序列的中间位置。然后再用同样的方法递归的排序划分这两部分。

快速排序代码实现：

public static void quickSort(int[] arr) {
	recursion(arr, 0, arr.length - 1);
}
public static void recursion(int[] arr, int low, int high) {
	if (low < high) {
		int pivot = partition(arr, low, high);
		recursion(arr, low, pivot - 1);
		recursion(arr, pivot + 1, high);
	}
}
//返回 基数 在数组 中的位置
public static int partition(int[] arr, int low, int high) {
	int pivot = arr[low];
	while (low < high) {
		while (low < high && arr[high] >= pivot)
			--high;
		arr[low] = arr[high];
		while (low < high && arr[low] < pivot)
			++low;
		arr[high] = arr[low];
	}
	arr[low] = pivot;
	return low;
}