算法 | 最坏复杂度 | 平均复杂度 | 最好复杂度 | 空间复杂度 |
---|---|---|---|---|
选择排序 | O($n^2$) | O($n^2$) | O($n^2$) | O(1) |
插入排序 | O($n^2$) | O($n^2$) | O($n$) | O(1) |
希尔排序 | O($nlog(n))$~O($n^2$) | O($n^{1.3}$) | O($n^2$) | O(1) |
冒泡排序 | O($n^2$) | O($n^2$) | O(n)(用交换 flag 改进) | O(1) |
快速排序 | O($n^2$) | O($nlog(n)$) | O($nlog(n)$) | O(log(n))~O(n) |
堆排序 | O($nlog(n)$) | O($nlog(n)$) | O($nlog(n)$) | O(1) |
归并排序 | O($nlog(n)$) | O($nlog(n)$) | O($nlog(n)$) | O(n) |
Java 实现
选择排序
- // 选择排序: 每次遍历找到数组中的最小值, 放到剩余数组最前面, 以此类推, 直到所有元素被排好
- public static void select_sort(int[] arr){
- int len=arr.length;
- long start=System.currentTimeMillis();
- for(int i=0;i<len;i++){
- for(int j=i+1;j<len;j++){
- if(arr[i]>arr[j]){
- swap(arr,i,j);
- }
- }
- }
- long end=System.currentTimeMillis();
- System.out.println("选择排序耗时(秒):"+(end-start));
- //toPrint(arr);
- }
插入排序
- // 插入排序: 用新的元素去与已经排序好的元素数组从尾部开始比较, 若比对应元素小, 则下标继续往前走, 直到找到比新元素小的元素, 然后将比新元素小的元素后面的全部元素后移, 插入新元素.
- public static int[] insert_sort(int[] arr){
- long start=System.currentTimeMillis();
- for(int i=0;i<arr.length;i++){
- int temp=arr[i];
- for(int j=i;j>0 && arr[j-1]>arr[j];j--){
- arr[j]=arr[j-1];
- arr[j-1]=temp;
- }
- }
- long end=System.currentTimeMillis();
- System.out.println("插入排序耗时(秒):"+(end-start));
- return arr;
- //toPrint(temparr);
- }
希尔排序
- // 希尔排序: 以 arr.length/2 为开始间隔, 并不断 / 2 缩小间隔的插入排序, 最后一次的循环比较 e 就是插入排序, 但是数组的绝大部分元素已经处于相对有序状态.
- public static int[] shell_sort(int arr[]){
- for(int gap=arr.length; gap>0 ; gap/=2){
- for(int i=gap;i<arr.length;i++){
- int temp=arr[i];
- for(int j=i;j>=gap && arr[j-gap]>arr[j];j-=gap){
- arr[j]=arr[j-gap];
- arr[j-gap]=temp;
- }
- }
- }
- return arr;
- }
冒泡排序
- // 冒泡排序: 比较相邻两个元素的大小, 决定是否交换位置, 每次循环可将一个最大值元素一直交换到最后面(或者将最小值一直交换到最前面), 以此类推. 用一个交换 flag 作优化可以将最优情况时间复杂度降到 O(n), 即只比较一轮.
- public static void bubble_sort(int[] arr){
- int len=arr.length;
- long start=System.currentTimeMillis();
- boolean swapFlag=true;
- for(int i=0;i<len;i++){
- if(swapFlag==false)
- break;
- swapFlag=false;
- for(int j=1;j<len-i;j++){
- if(arr[j-1]>arr[j]){
- swap(arr,j-1,j);
- swapFlag=true;
- }
- }
- }
快速排序
- // 思路: 每一次排序, 将首元素 (arr[0]) 交换到这样的位置, 即它所在位置往右的所有元素都不小于它, 且它所在位置往左的所有元素都不大于它. 完成这一步, 只需要将首元素不断地从右往左遍历找比它小的, 然后从左往右找比它大的, 找到即交换位置, 一直到从两个方向都再也找不到一个可以交换的元素, 一轮排序结束. 接着用递归的方式排序剩下的两半.
- public static void quickSort(int[] arr,int start,int end){
- if(start>=end)
- return;
- boolean leftFlag=false,rightFlag=false;
- int pivot=start;
- System.out.println("hehe");
- while(!(leftFlag && rightFlag)){
- leftFlag=true;rightFlag=true;
- // 第一轮: 第一个元素从右边开始找第一个比它小的元素, 与之交换位置
- for(int i=end;i>=start;i--){
- if(arr[pivot]<arr[i]){
- exchange(arr, pivot, i);
- pivot=i;
- leftFlag=false;
- }
- }
- System.out.println("循环");
- for(int i=start;i<=end;i++){
- if(arr[pivot]<arr[i]){
- exchange(arr, pivot, i);
- pivot=i;
- rightFlag=false;
- }
- }
- }
- quickSort(arr, start, pivot-1);
- quickSort(arr, pivot+1,end);
- }
堆排序
归并排序
- // 思路: 将数组不断划分为更小的两个数组的组合(递归), 当划分到最小的粒度时, 即两个数之间的比较与位置交换, 然后不断将两个小的数组融合成大的数组(merge 方法).
- public static void merge_sort(int[] arr,int low,int high){
- if(high>low){
- int pivot=(high+low)/2;
- merge_sort(arr,low,pivot);
- merge_sort(arr,pivot+1,high);
- merge(arr,low,pivot,high);
- }
- }
- private static void merge(int[] arr,int low,int pivot,int high){
- int[] temp=new int[high-low+1];
- int i=low,j=pivot+1;
- int count=0;
- while(i<=pivot && j<=high){
- if(arr[i]>arr[j]){
- temp[count++]=arr[j];
- j++;
- }
- else{
- temp[count++]=arr[i];
- i++;
- }
- }
- while(i<=pivot){
- temp[count++]=arr[i];
- i++;
- }
- while(j<=high){
- temp[count++]=arr[j];
- j++;
- }
- for(int x=0;x<temp.length;x++){
- arr[low+x]=temp[x];
- }
- }
来源: http://www.bubuko.com/infodetail-2674952.html