排序算法

发表于 分类于 阅读次数：
本文字数： 9.3k 阅读时长 ≈ 8 分钟

基础算法

快速排序

两边划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void fastSort(int[] arr,int l, int r){
       if(l >= r) return ;
       int i = l-1, j = r +1;
       int x = arr[l];
       while(i < j){
           do{i++;}while(arr[i] < x);
           do{j--;}while(arr[j] > x);
            if(i < j){
                swap(arr, i, j);
            }
       }
       fastSort(arr,i,j);
       fastSort(arr, j+1, r);
    }

归并排序

双路 两边合并 稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package data;

public class test2{
    public static void main(String[] args) {
        
    }
    private static void totalMergeSort(int[] arr){
        if(arr == null || arr.length < 2)
        return ;
        mergeSort(arr,0,arr.length -1);
    }
    private static void mergeSort(int[] arr, int l, int r){
        if(l >= r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr,l,r,mid);
    }
    private static void merge(int[] arr, int l, int r, int mid) {

        int[] temp = new int[r - l + 1];
        int i = l , j = mid + 1;
        int idx = 0;
        while(i <= mid && j <= r){
            temp[idx++] = arr[j] <= arr[i] ? arr[j++] : arr[i++];
        }
        while(i <=mid) temp[idx++] = arr[i++];
        while(j <=r) temp[idx++] = arr[j++];

        idx = 0;
        while(l <= r)
            arr[l++] = temp[idx++];
    }
}

归并最小和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package data;

public class test2{
    public static void main(String[] args) {
         int[] arr = {4,1,3,5,0,6};
        // totalMergeSort(arr);
        // 

        // int max = recursionSort(arr, 0, arr.length-1);
        // System.out.println(max);

         //int[] arr = {4,1,3,5,0,6};
        // int res = TotalSmallMerge(arr);

        System.out.println(totalMergeSort(arr));
        for (int var : arr) {
                System.out.print(var+" ");
            }
        
    }
    private static int totalMergeSort(int[] arr){
        if(arr == null || arr.length < 2)
            return 0;
        int res = mergeSort(arr,0,arr.length -1);
        return res;
    }
    private static int mergeSort(int[] arr, int l, int r){
        if(l >= r) return 0;
        int mid = l + ((r - l) >> 1);
        int left = mergeSort(arr, l, mid);
        int right = mergeSort(arr, mid + 1, r);
        int total = merge(arr,l,r,mid);
        return left+right+total;
    }
    private static int merge(int[] arr, int l, int r, int mid) {

        int[] temp = new int[r - l + 1];
        int res = 0;
        int i = l , j = mid + 1;
        int idx = 0;
        while(i <= mid && j <= r){
            res += arr[j] >= arr[i] ? (r-j+1)*arr[i] : 0;
            temp[idx++] = arr[j] <= arr[i] ? arr[j++] : arr[i++];
        }
        while(i <=mid) temp[idx++] = arr[i++];
        while(j <=r) temp[idx++] = arr[j++];

        idx = 0;
        while(l <= r)
            arr[l++] = temp[idx++];
        return res;
    }
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static void heap(int[] arr){

        //1.大根堆的插入
        int heapLength = arr.length;
        for(int i = 0 ; i < heapLength; i++)
            heapInsert(arr,i);
        //2.大根堆调整
        swap(arr, 0, --heapLength);
        while(heapLength > 0){
            heapify(arr,0,heapLength);
            swap(arr, 0, --heapLength);
        }
    }
    private static void heapInsert(int[] arr, int index){
            while(arr[index] > arr[(index-1) /2]){
                swap(arr, index, (index-1) /2);
                index = (index-1)/2;
            }
    }
    private static void heapify(int[] arr, int index,int size){
        int left = index * 2 + 1;
        while( left < size){
            int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left;
            largest = arr[index] > arr[largest] ? index : largest;
            if(largest == index)
                break;
            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

对象排序

Comparator 类的实现

Arrays.sort(,)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Student{
    public int id;
    public String name;

    public Student(int i, String string) {
        this.id = i;
        this.name = string;
    }
    public String stuPrint(){
        return new String("id "+id+ " name "+ name);
    }

}
class IdAscendingComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.id - o2.id;
    }
    
}
public class helo2{
    public static void main(String[] args) {
        //List<Student> myList = new ArrayList<>();
        Student stu1 = new Student(1,"miki");
        Student stu2 = new Student(2,"miki1");
        Student stu3 = new Student(3,"miki1");
    
        Student[] myList = new Student[] { stu1,stu2,stu3 };
        Arrays.sort(myList, new IdAscendingComparator());

        for (Student var : myList) {
            System.out.println(var.stuPrint());
        }
    }
}

二分

找一边不满足性质 一边满足性质的 \mid check-》范围 + 更新方位

1
2


冒泡排序

交换排序： o(n) -> o(n^2)

1
2
3
4
5
6
7
8
9
10
11
private static void bubbleSort(int[] arr) {
       if(arr == null || arr.length < 2)
           return;
       for(int end = arr.length -1; end > 0 ; end--){
           for(int j = 0 ; j < end; j++){
               if(arr[j] > arr[j+1]){
                   swap(arr, j, j + 1);
               }
           }
       }
   }

选择排序

选择排序 o(n^2) -> o(n^2)

1
2
3
4
5
6
7
8
9
10
private static void selectSort(int[] arr){
       for(int i = 0 ; i < arr.length - 1; i++){
           int mix = arr[i];
           for(int j = i+1; j < arr.length - 1; j++){
               if(arr[j] < mix){
                   swap(arr,mix,arr[j]);
               }
           }
       }
   }

插入排序

插入排序 o(n) -> o(n^2)

1
2
3
4
5
6
7
8
9
private static void insertSort(int[] arr){
        if(arr == null || arr.length < 2)
            return ;
        for(int i = 1; i < arr.length - 1; i++){
            for(int j = i -1; j >=0 && arr[j] > arr[j+1]; j++){
                swap(arr, arr[j], arr[j+1]);
            }
        }
    }

桶排序

空桶问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package data;

public class j106{
    public static void main(String[] args) {
        System.out.println("hlll");

        int[] arr = {1,5,6,8,55,7};
        //System.out.println(indexBox(1, arr.length, 55, 1));
        System.out.println(masGaps(arr));
    }

    public static int masGaps(int[] arr){

        //创桶
        int len = arr.length;
        boolean[] box = new boolean[len+1];
        int [] maxBox = new int[len+1];
        int [] minBox = new int[len+1];

        int maxResult = Integer.MIN_VALUE;
        int minResult = Integer.MAX_VALUE;

        for(int i = 0; i < len; i++){
            maxResult = Math.max(maxResult,arr[i]);
            minResult = Math.min(minResult,arr[i]);
        }

        //设桶
        for(int i = 0 ; i < len ; i++){

            int index = indexBox(arr[i],maxResult,minResult,len);
            maxBox[index] = box[index] ? Math.max(maxBox[index], arr[i]) : arr[i];
            minBox[index] = box[index] ? Math.min(minBox[index],arr[i]) : arr[i];

            box[index] = true;
        }

        //拿桶
        int res = Integer.MIN_VALUE;
        int maxLeft = maxBox[0];
        int minRight = 0;
        for(int i = 1 ; i <= len; i++){
            if(box[i])
            {
                minRight = minBox[i];
                res = Math.max(res, minRight - maxLeft);
                maxLeft = maxBox[i];
            }
        }
        return res;
    }
    public static int indexBox(int num, int max, int min,int len){
        return (num - min)*len / (max - min);
    }
}

数组实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package three;

import java.lang.reflect.Array;

/**
 * 数组实现栈  泛型
 * array = (T[])Array.newInstance(type,)
 */
public class ArrayToStack<T>{

    private int index;
    private int capacity;
    private T[] array;
    
    public ArrayToStack(Class<T> type) {
        this.index = 0;
        this.capacity = 5;
        this.array =  (T[])Array.newInstance(type, this.capacity);
    }

    //push
    public Integer push(T obj) {
       if(this.index == this.capacity){
           throw new ArrayIndexOutOfBoundsException("The Stack is full");
       }
       return (Integer) (array[index++] = obj);
    }
    //pop  
    public Integer pop(){
       if(this.index == 0 ){
           throw new ArrayIndexOutOfBoundsException("The Stack is Empty");
       }
       return (Integer) array[--index];
    }
    //peek
    public Integer peek(){
        if(this.index != 0)
        {
            return (Integer) array[this.index - 1];
        }
        else{
            return null;
        }
    }

    public static void main(String[] args) {

        ArrayToStack<Integer> myArray = new ArrayToStack<>(Integer.class);
        for(int i = 0 ; i < 5; i++){
            myArray.push(i);
            System.out.println(myArray.peek());
        }
        for(int i = 0 ; i < 5; i++){   
            System.out.println(myArray.pop());
        }
    }
}
相关文章
0%