面试中一定要准备的7种排序算法

1.冒泡排序

	public int[] bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = arr.length - 1; j > i; j--) {
				if (arr[j - 1] > arr[j]) {
					int temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
				}
			}
		}
		return arr;
	}

冒泡排序的改进

// 稍微优化一下,对于排序好的如123456789，会一直交换多次
	public void bubbleSortBetter(int[] arr) {
		// 一次循环中如果没有交换过元素，就说明已经排好了
		boolean isSorted = true;
		for (int i = 0; i < arr.length; i++) {
			for (int j = arr.length - 1; j > i && isSorted; j--) {
				isSorted = false;
				if (arr[j - 1] > arr[j]) {
					int temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
					isSorted = true;
				}
			}
		}
	}

2.选择排序

	public void chooseSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int min = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[min] > arr[j]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = arr[min];
				arr[min] = arr[i];
				arr[i] = temp;
			}
		}
	}

3.插入排序

public void insertSort(int[] arr) {
		int j;

		for (int i = 1; i < arr.length; i++) {
			// 优化条件
			if (arr[i] < arr[i - 1]) {
				int temp = arr[i];
				// 是从最左边开始，比较的同时还要移动
				for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
					arr[j + 1] = arr[j];
				}
				arr[j + 1] = temp;
			}
		}
	}

4.希尔排序

	// 排序是不稳定的，最坏时间复杂度O（n^1.5）,平均时间复杂度O（nlogn）；
	// 步长一般都用2，但是最后只要保证gap=1就可以。
	public void shellSort(int[] arr) {
		int j;
		int gap = arr.length / 2;
		while (gap >= 1) {
			// 下面就是一个插入排序过程，只是每个过程都是有间隔
			for (int i = gap; i < arr.length; i++) {
				int temp = arr[i];
				for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
					arr[j + gap] = arr[j];
				}
				arr[j + gap] = temp;
			}
			gap = gap / 2;
		}
	}

5.堆排序

// 堆的删除，只能删除A【0】的节点，将交换后的节点和儿子比较，选最小的一个作为头节点。
	// 从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
	public void heapAdjust(int[] arr, int i, int n) {
		// i表示当前节点开始调整，主要是通用性
		int temp = arr[i];
		int index = 2 * i + 1;
		while (index < n) {
			// 找到左右儿子最小值的索引
			if (arr[index] < arr[index + 1]) {
				index++;
			}
			if (temp < arr[index]) {
				break;
			}
			// 将最小儿子上移动
			arr[i] = arr[index];
			i = index;
			index = 2 * i + 1;
		}
		// 以为temp一直没有变，而且用来作为比较的参考值，
		// 因此不交换而用这种方式就可以。
		arr[index] = temp;
	}


// 堆化数组
	public void makeArrayToMinHeap(int[] arr, int n) {
		// 因为叶子节点不用参与重组，相当于是已经建好的堆
		// 这就用上了之前的堆的删除的那个函数，删除那个函数因为n
		// n不变时就用来当调整使用了n / 2 - 1最后一个非叶子节点
		for (int i = n / 2 - 1; i >= 0; i--)
			heapAdjust(arr, i, n);
	}

public void heapSort(int[] arr) {
		// 第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。
		// 第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，
		// 重复这样的操作直到A[0]与A[1]交换。
		for (int i = arr.length - 1; i >= 1; i--) {
			int temp = arr[i];
			arr[i] = arr[0];
			arr[0] = temp;
			heapAdjust(arr, 0, i);
		}

	}

6.快速排序

public void quickSort(int[] arr, int low, int high) {
		if (low >= high) {
			return;
		}
		int left = low;
		int right = high;
		int mid = arr[low];
		
		while (low < high) {
			// 必须先从高位开始
			while (low < high && arr[high] >= mid) {
				high--;
			}
			arr[low] = arr[high];
			while (low < high && arr[low] <= mid) {
				low++;
			}
			arr[high] = arr[low];
		}
		arr[low] = mid;

		quickSort(arr, left, low - 1);
		quickSort(arr, low + 1, right);

	}

7.归并排序

public void mergeSort(int[] arr) {
		// 必须要从外面创建temp传进去
		int[] temp = new int[arr.length];
		mergeArray(arr, 0, arr.length - 1, temp);
	}

	public void mergeArray(int[] arr, int low, int high, int[] temp) {

		// 注意递归出口
		if (low < high) {
			int mid = (low + high) / 2;
			mergeArray(arr, low, mid, temp);
			mergeArray(arr, mid + 1, high, temp);
			merge(arr, temp, low, mid, high);
		}
	}

	public void merge(int[] arr, int[] temp, int low, int mid, int high) {
		int left1 = low;
		int left2 = mid + 1;
		int k = 0;
		while (left1 <= mid && left2 <= high) {
			if (arr[left1] > arr[left2]) {
				temp[k++] = arr[left2++];
			} else {
				temp[k++] = arr[left1++];
			}
		}
		while (left2 < high) {
			// 不会发生越界，因为left2也是先赋值，再++；
			temp[k++] = arr[left2++];
		}
		while (left1 < mid) {
			temp[k++] = arr[left1++];
		}
		System.arraycopy(arr, low, temp, 0, temp.length);
	}