经典排序算法

本次介绍几种经典排序算法以及Java实现代码
1.冒泡排序
冒泡排序是属于相邻两两比较进行排序的一种，由于其实现是经过1到n-1轮排序，
通过比较相邻的两个数，大的向下继续与相邻的进行比较，直到找到正确的顺序位置。

1
2
3
4
5
6
7
8
9
10
11
public void bubbleSort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {//比较轮次，经过n-1次比较
			for (int j = 0; j < a.length - 1 - i; j++) {//每次比较相邻的两个数，大的向后移动
				if (a[j] > a[j + 1]) {
					int temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}
		}
	}

2.选择排序
选择排序是经过n-1次选择，每次选中一个数，作为最小基数与剩余的数进行比较，然后选出最小数，与最小基数交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void selectionSort(int[] a) {
		for (int p = 0; p < a.length - 1; p++) {
			int minIndex = p;
			for (int j = p + 1; j < a.length; j++) {
				if (a[minIndex] > a[j]) {
					a[minIndex] = a[j];
					minIndex = j;
				}
			}
			if (minIndex != p) {
				int temp = a[p];
				a[p] = a[minIndex];
				a[minIndex] = temp;
			}
		}
	}

3.插入排序
插入排序也是两两比较达到排序目的的一种排序算法。插入排序是经过n-1轮排序，
对于p=1到n-1趟，插入排序保证从位置0到p上的元素为以排序状态。插入排序利用了：已知位置0到位置p-1上的元素已经处于排过序的状态。

1
2
3
4
5
6
7
8
9
10
public void insertionSort(int[] a) {
		int j;
		for (int p = 1; p < a.length; p++) {//排序轮次n-1次
			int temp = a[p];//前p-1的位置已经排好序，取出位置p的数据
			for (j = p; j > 0 && temp < a[j - 1]; j--) {//比较p和p-1上的大小，如果p位置上的大，则交换两个位置上的数，否则，继续向前比较，直到可以将位置p上的数能够插入的合适位置
				a[j] = a[j - 1];
			}
			a[j] = temp;
		}
	}

4.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void quickSort(int[] arr, int low, int high) {
		if(low < high){
			int pivot = partation(arr, low, high);
			quickSort(arr, low, pivot - 1);
			quickSort(arr, pivot + 1, high);
		}
		
}

public int partation(int[] arr, int low, int high){
	while(low < high){
		int pivot = arr[low];
		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;
}