我手写排序算法，面试官惊了

一、冒泡排序Bubble Sort

1.1、原理

1. 比较相邻的元素，如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，一轮过后最后的元素就是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个，直到没有任何一对数字需要比较。

1.2、时间复杂度

O(n^2)

1.3、原理图

1.4、代码实现

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

二、快速排序Quick Sort

2.1、原理

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.2、时间复杂度

O(nlogn)

2.3、原理图一

2.3、代码实现一

public static int[] sort(int[] arr,int start,int end) {
	int i = start;
	int j = end;
	int val = arr[start];
	while(i<j) {
		while(arr[i]<val && i<j) {
			i++;
		}
		while(arr[j]>val && i<j) {
			j--;
		}
		if(arr[i] == arr[j] && i<j) {
			//这里既可以是i++也可以是j--，但不能同时存在
			//i++表示等于的值放左边，j--表示等于的值放右边
			//不能同时存在的意思就是，相等的值只能放在一边
			i++;
		}else {
			int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
		}
	}
	if(j+1 < end) {
		sort(arr, j+1, end);
	}
	if(i-1 > start) {
		sort(arr, start, i-1);
	}
	return arr;
}

2.4、原理图二

2.5、代码实现二

public static int[] sort2(int[] arr,int start,int end) {
	int i = start;
	int j = end;
	//挖好第一个坑，arr[start]，填入小的数
	int val = arr[start];
	while(i<j) {
		//因为第一个坑是寻找小的数，所以从后开始找
		while(arr[j] > val && i<j) {
			j--;
		}
		if(i < j) {
			//找到小的数arr[j]，把arr[j]填入i中，j成为下一个坑。
			arr[i] = arr[j];
			//i坑已填，找下一个
			i++;
		}
		//j坑需要入大的数，所以从前开始找
		while(arr[i]<val && i<j) {
			i++;
		}
		if(i<j) {
			//找到大的数arr[i]，把arr[i]填入j中，i成为下一个坑。
			arr[j] = arr[i];
			//j坑已填，找下一个
			j--;
		}
	}
	//循环结束之后j==i,i所在的位置就是最后一个坑，把arr[start]填入。
	//至此i的左边都小于arr[start]，右边都大于arr[start]
	arr[i] = val;

	if(j+1 < end) {
		sort2(arr, j+1, end);
	}
	if(i-1 > start) {
		sort2(arr, start, i-1);
	}
	return arr;
}