音乐播放器
琢钰
 
文章 标签
12

Powered by X2 | Theme: Fog
载入天数...
载入时分秒...
总访问量:  |   访问人数:
御风飞行中...

总复习03-几种基本的排序算法

  热度: loading...

几种基本的排序算法

  • 冒泡排序

     O(n2)   O(n)   O(n2)            :O(1)时间复杂度:~平均:O(n^2)~~~最好:O(n)~~~最坏:O(n^2)~~~~~~~~~~~~空间复杂度:O(1)

    import java.util.Arrays;
    
    public class BubbleSort {
    
        public static void main(String[] args) {
            int a[] = {5, 4, 8, 7, 9, 3};
            BubbleSort bubbleSort = new BubbleSort();
            System.out.println(Arrays.toString(bubbleSort.bubble(a)));
        }
    
        public int[] bubble(int[] arr) {
            for (int i = arr.length-1; i > 0 ; i--) {
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[j+1]) {
                        int temp;
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
            return arr;
        }
    }
    
    
  • 选择排序

     O(n2)   O(n2)   O(n2)            :O(1)时间复杂度:~平均:O(n^2)~~~最好:O(n^2)~~~最坏:O(n^2)~~~~~~~~~~~~空间复杂度:O(1)

    import java.util.Arrays;
    
    public class SelectSort {
        public static void main(String[] args) {
            int a[] = {5, 4, 8, 7, 9, 3,62,11,88};
            SelectSort selectSort = new SelectSort();
            System.out.println(Arrays.toString(selectSort.select(a)));
        }
    
        public int[] select(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = i+1; j < arr.length; j++) {
                    if (arr[j] < arr[i]) {
                        int temp;
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
    
            }
            return arr;
        }
    }
    
  • 插入排序

     O(n2)   O(n)   O(n2)            :O(1)时间复杂度:~平均:O(n^2)~~~最好:O(n)~~~最坏:O(n^2)~~~~~~~~~~~~空间复杂度:O(1)

    import java.util.Arrays;
    
    public class InsertSort {
    
        public static void main(String[] args) {
            int a[] = {5, 4, 8, 7, 9, 3, 62, 11, 88};
            InsertSort insertSort = new InsertSort();
            System.out.println(Arrays.toString(insertSort.charu(a)));
        }
    
        public int[] charu(int[] arr) {
            for (int i = 1; i < arr.length; i++) {
                int j;
                int temp = arr[i];
                for (j = i; j >0; j--) {
                    if (arr[j-1] > temp) {
                        arr[j] = arr[j-1];
                    } else {
                        break;
                    }
                }
                arr[j] = temp;
            }
            return arr;
        }
    }
    
  • 快速排序

     O(nlog2n)   O(nlog2n)   O(n2)            :O(nlog2n)时间复杂度:~平均:O(nlog_2n)~~~最好:O(nlog_2n)~~~最坏:O(n^2)~~~~~~~~~~~~空间复杂度:O(nlog_2n)

    import java.util.Arrays;
    
    public class QucikSort {
        public static void main(String[] args) {
            int[] arr = {6,9, 8, 7, 6, 5,5,55, 4, 3, 5,2, 1, 0};
            new QucikSort().quickSort(arr, 0, arr.length - 1);
            System.out.println("排序结果:" + Arrays.toString(arr));
        }
    
        void quickSort(int s[], int l, int r)
        {
            if (l < r)
            {
                int i = l, j = r, x = s[l];
                while (i < j)
                {
                    while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                        j--;
                    if(i < j)
                        s[i++] = s[j];
    
                    while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                        i++;
                    if(i < j)
                        s[j--] = s[i];
                }
                s[i] = x;
                quickSort(s, l, i - 1); // 递归调用
                quickSort(s, i + 1, r);
            }
        }
    }