Algo_Practice/SortingPractice.java at main · Ring-Yew/Algo_Practice · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
public class SortingPractice {
    public static void main(String[] args) {

    }
    public static void merge(int[] nums, int left, int mid, int right)
    {
        //left interval is [left,mid], and right interval is [mid+1,right]
        int[] temp = new int[right-left+1];
        int i = left, j = mid+1, k = 0;
        while(i <= mid && j <= right)
        {
            if(nums[i]<nums[j])
            {
                temp[k] = nums[i];
                i++; k++;
            }
            else
            {
                temp[k] = nums[j];
                k++; j++;
            }
        }
        for(;j <= right; j++, k++)
            temp[k] = nums[j];
        for(; i <= mid; i++, k++)
            temp[k] = nums[i];
        for(k = 0; k<temp.length; k++)
            nums[left+k] = temp[k];

    }
    public static void mergeSort(int[] nums, int left, int right)
    {
        if(left>=right) return;
        int mid = left + (right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    public static int partition(int[] nums, int left, int right)
    {
        /*Use nums[left] as pivot */
        int i = left, j = right;
        while(i<j)
        {
            while(i<j && nums[j]>=nums[left])
                j--;
            while(i<j && nums[i]<=nums[left])
                i++;
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int temp = nums[i];
        nums[i] = nums[left];
        nums[left] = temp;
        return i; //return index of pivot
    }
    public static void quickSort(int[] nums, int left, int right)
    {
        if(left >= right)
            return;
        int pivot = partition(nums, left,right);
        quickSort(nums, left, pivot-1);
        quickSort(nums, pivot+1, right);

    }
    public static void insertionSort(int[] nums)
    {
        int n = nums.length;
        for(int i = 1; i < n; i++)
        {
            int temp = nums[i];
            int j = i-1;
            for(; j >= 0; j--)
            {
                if(nums[j]>temp)
                    nums[j+1] = nums[j];
                else break;
            }
            nums[j+1] = temp;
        }
    }
    public static void bubbleSort(int[] nums)
    {
        int n = nums.length;
        for(int j = n-1; j>=0; j--)
        {
            for(int i=0; i<j; i++)
            {
                if(nums[i]>nums[i+1])
                {
                    int temp = nums[i];
                    nums[i] = nums[i+1];
                    nums[i+1] = temp;
                }
            }
        }
    }
    public static void selectionSort(int[] nums)
    {
        int n = nums.length;
        for(int i = 0; i < n; i++)
        {
            int minIndex = -1;
            int min = Integer.MAX_VALUE;
            for(int j = i; j < n; j++)
            {
                if(nums[j]<=min){
                    minIndex = j;
                    min = nums[j];
                }
            }
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }
    public static void swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}