排序(冒泡/快速/归并)
冒泡排序
-
时间复杂度为 O(n^2)
-
原理
- 比较相邻的元素. 如果第一个比第二个大,就交换他们两个.
- 依次比较每一对相邻的元素—>结果 : 最后的元素是这组数中最大的
- 重复上述步骤 , 除了最后一个[]因为最后一个已经是排好序的了(这组数中最大的那个)]
- 持续对越来越少的元素进行如上步骤 , 直到没有任何一对数字需要比较
-
核心代码
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]) { //把大的往后放int t = arr[j];arr[j] = arr[j+1];arr[j+1] = t;}}}}
快速排序
- 归并排序和快速排序都是基于“分而治之”的算法思想
public static int[] qSort(int arr[],int start,int end){int pivot = arr[start]; //一般定义arr数组的首元素为key值int i = start; int j = end;while(i<j){//从左往右找,直到找到一个大于等于key值的while(i<j && arr[i]<pivot){i++; } //从右往左找，直到找到一个小于等于key值的while(i<j && arr[j]>pivot){j—-; } if(i<j && arr[i]==arr[j]){ //如果两值相等，那么令左侧指针继续向后移i++; }else{ //如果两值不同，就交换两值int t = arr[i];arr[i] = arr[j];arr[j] = t; }}if(i-1>start) arr=qSort(arr,start,i-1); //递归，将小于key值的那些排序。并将这部分排完序的数组（原数组的一部分）赋值给原数组if(j+1<end) arr=qSort(arr,j+1,end); //递归，将大于key值的那些排序。同上return arr;
}
归并排序
- 时间复杂度 ：O(nlogn)
- 速度仅次于快速排序
归并 就是先将带排序的数组不断拆分，指导拆分到只剩一个元素的时候，这时我们再把他们合并为两个有序的数组，得到长度更长的有序数组。然后，按照这样的思路，一层一层的合并，直到整个数组有序。 - 怎么合并？
要借助一个和原数组等长的新数组（这也是个典型的 以空间换时间的 做法）
// import java.util.Arrays;public class Main{public static void main(String[] args){int[] arr = {1,4,3,7,14,6,10};// System.out.println(Arrays.toString(arr));sortArray(arr);for(int i=0;i<arr.length;i++){System.out.print(arr[i]+" ");}}//归并排序的入口public static int[] sortArray(int[] arr){//定义一个辅助数组tempint[] temp = new int[arr.length];//进行归并排序mergeSort(arr,0,arr.length-1,temp);//返回排好序的原数组return arr;}//归并排序//实现归并的'分'public static void mergeSort(int[] arr,int left,int right,int[] temp){//如果只有一个元素，就不需要继续划分（只有一个元素的区间，本来就是有序的）// if(left == right) return;//当left < right 说明该区间是由一组数组成，需要继续划分if(left < right){int mid = (left+right)/2; //这段区间的中值，用来划分左右区域mergeSort(arr, left, mid, temp); //递归划分左半区mergeSort(arr, mid+1, right, temp); //递归划分右半区//合并已经排序的部分（左半区和右半区）（从只有一个元素的区间开始）merge(arr,left,mid,right,temp);}}
//实现归并的'合'
//arr是原数组；left是左半区的起始位置；mid是左半区的结束位置；right是右半区的结束位置；temp是辅助数组public static void merge(int[] arr,int left,int mid,int right,int[] temp){int i = left; //左半区的起始位置int j = mid+1; //右半区的起始位置int k = left; //辅助数组的位置索引//合并//在左半区的位置索引范围内，和右半区的位置索引范围内，比较左右半区对应索引位置得的数值的大小，小的先放入temp数组中while(i<=mid && j<=right){//用三元运算符 更简洁 和下面的if else语句一个意思temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];/*if(arr[i]<arr[j]) //左半区剩余第一个元素更小temp[k++] = arr[i++]; //意思是：先让temp[h] = arr[i]；再让k++，i++；else //右半区剩余第一个元素更小temp[k++] = arr[j++];*/}//合并剩余元素（当其中一个半区的位置索引结束时，另一个半区可能还有剩余有序的元素--》直接合并到temp数组中即可）//合并左半区剩余元素while(i <= mid)temp[k++] = arr[i++];while(j <= right)temp[k++] = arr[j++];//temp数组 复制回 arr数组// for(int q=0;q<temp.length;q++){// arr[q] = temp[q];// }while(left <= right){arr[left] = temp[left];left++;}}
}