排序算法
1.冒泡排序：
冒泡排序一共要进行(n-1)次循环,每一次循环都要进行当前n-1次比较
所以一共的比较次数是:
(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2;
所以冒泡排序的时间复杂度是 O(n2)，空间复杂度O（1）
所以一共的比较次数是:
(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2;
所以冒泡排序的时间复杂度是 O(n2)，空间复杂度O（1）
int a[]= {6,5,0,4,2,1,3,9,8};
int n=a.length;
for(int i=0;i<n-1;i++) {
boolean flag=false;
for(int j=0;j<n-i-1;j++) {
if(a[j]>a[j+1]) {
int t=a[j+1];
a[j+1]=a[j];
a[j]=t;
flag=true; //此次循环进行了交换
}
}
if(!flag) //已经有序，可直接退出
break;
}
for(int i:a) {
System.out.print(i+" ");
} 2.快速排序
时间复杂度为O(nlogn)
public static void main(String[] args) {
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
public static void quickSort(int[] arr,int low,int high) {
if(low>high){
return;
}
int tmp=arr[low];
int i=low,j=high;
while(i<j) {
while(arr[j]>=tmp && i<j) {
j--;
}
while(arr[i]<=tmp && i<j) {
i++;
}
//交换 i j两个位置的元素
if(i<j) {
int t=arr[j];
arr[j]=arr[i];
arr[i]=t;
}
}
arr[low]=arr[i];
arr[i]=tmp;
quickSort(arr, low, j-1);
quickSort(arr, j+1, high);
}
