ToyanのBlog HomeArchivesTagsCategories
排序算法
|algorithmsort
Word count: 1k|Reading time: 6 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
package Sort;

/**
 * @Author: hta
 * @Date: 2018/03/26
 * @Time: 22:03
 * @Description: 冒泡排序
 * o(n^2)
 */
public class bubbleSort {
    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }

            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 7, 9, 5};
        bubbleSort(nums);
        for (int num: nums) {
            System.out.print(num);
        }
    }
}
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
package Sort;

/**
 * @Author: hta
 * @Date: 2018/03/26
 * @Time: 21:31
 * @Description: 堆排序
 * o(nlogn)
 */
// 先建立最大堆，然后排序
public class heapSort {
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 7, 9, 5};
        int index = nums.length;
        heapify(nums);
        while (index > 0) {
            int tmp = nums[index - 1];
            nums[index - 1] = nums[0];
            nums[0] = tmp;

            index--;
            helper(nums, index, 0);
        }
        for (int num: nums) {
            System.out.print(num);
        }
    }
    private static void heapify(int[] nums) {
        for (int i = (nums.length - 1) / 2; i >= 0; i--) {
            helper(nums, nums.length, i);
        }
    }
    private static void helper(int[] nums, int len, int k) {
        while (k < len) {
            int largest = k;
            if (k * 2 + 1 < len && nums[largest] < nums[k * 2 + 1]) {
                largest = k * 2 + 1;
            }
            if (k * 2 + 2 < len && nums[largest] < nums[k * 2 + 2]) {
                largest = k * 2 + 2;
            }
            if (k == largest) {
                break;
            }
            int tmp = nums[largest];
            nums[largest] = nums[k];
            nums[k] = tmp;

            k = largest;
        }
    }
}
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 Sort;

/**
 * @Author: hta
 * @Date: 2018/03/26
 * @Time: 20:03
 * @Description: 希尔排序
 * o(n^1.5)
 */
public class insertShell {
    public static void insertSort(int[] nums) {
        int n = nums.length;
        int len = n / 2;
        while (len >= 1) {
            for (int i = 0; i < n - len; i++) {
                for (int j = 0; j <= i; j++) {
                    if (nums[j] > nums[j + len]) {
                        int tmp = nums[j];
                        nums[j] = nums[j + len];
                        nums[j + len] = tmp;
                    }
                }
            }
            len /= 2;
        }
    }
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 7, 9, 5};
        insertSort(nums);
        for (int num: nums) {
            System.out.print(num);
        }
    }
}
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
package Sort;

/**
 * @Author: hta
 * @Date: 2018/03/26
 * @Time: 19:52
 * @Description: 直接插入排序，当前位置与它前面的数字比较，看插入哪一个位置
 * o(n^2)
 */
public class insertSort {
    public static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 7, 9, 5};
        insertSort(nums);
        for (int num: nums) {
            System.out.print(num);
        }
    }
}
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
package Sort;

/**
 * Created by hta on 17-5-5.
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 4, 5};
        quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }

    }
    public static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int pivot = nums[(start + end) / 2];
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        quickSort(nums, start, right);
        quickSort(nums, left, end);
    }
}
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
package Sort;

/**
 * author: hta
 * since: 上午10:45 17-5-6
 * time: O(nlogn)
 * param: int[] nums, int[] temp, int start, int end
 * return: void
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] nums = {2,3,1,55,6,4,7,3,0};
        int[] temp = new int[nums.length];
        mergeSort(nums, temp, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }

    }
    public static void mergeSort(int[] nums, int[] temp, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int mid = (start + end) / 2;
        mergeSort(nums, temp, left, mid);
        mergeSort(nums, temp, mid + 1, right);
        merge(nums, temp, start, mid, end);
    }
    public static void merge(int[] nums, int[] temp, int start, int mid, int end) {
        int leftIndex = start;
        int rightIndex = mid + 1;
        int index = start;
        while (leftIndex <= mid && rightIndex <= end) {
            if (nums[leftIndex] <= nums[rightIndex]) {
                temp[index++] = nums[leftIndex++];
            } else {
                temp[index++] = nums[rightIndex++];
            }
        }
        while (leftIndex <= mid) {
            temp[index++] = nums[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = nums[rightIndex++];
        }
        for (int i = start; i <= end; i++) {
            nums[i] = temp[i];
        }
    }
}
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
package Sort;

/**
 * @Author: hta
 * @Date: 2018/03/26
 * @Time: 20:59
 * @Description: 简单选择排序
 * o(n^2)
 */
public class selectSort {
    public static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < min) {
                    int tmp = nums[j];
                    nums[j] = min;
                    min = tmp;
                }
            }
            nums[i] = min;
        }
    }
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 7, 9, 5};
        selectSort(nums);
        for (int num: nums) {
            System.out.print(num);
        }
    }
}
Author: Toyan
Link: https://toyan.top/algorithm-sort/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
算法
支付宝打赏
微信打赏