JAVA实现三种排序算法+二分查找算法

忘是亡心i 2021-12-12 13:45 266阅读 0赞

冒泡排序  
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。   
其核心思想是：   
对于一组需要排序的数字，依次将个位置上的数字与逐一与其之后的数字进行比较，如果他们的顺序错误就把他们交换过来。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

package com.wip.sorting;  
import java.util.Arrays;  
public class BubbleSort \{  
    /\*\*  
     \* 冒泡排序  
     \* @param arr       需要排序的数组元素  
     \* @param asc       是否升序  
     \*/  
    public static void sort(int\[\] arr, boolean asc) \{  
        for (int i = 0; i < arr.length; i++) \{  
            for (int j = i+1; j < arr.length; j++) \{  
                if (asc) \{  
                    if (arr\[i\] > arr\[j\]) \{  
                        swap(arr,i,j);  
                    \}  
                \} else \{  
                    if (arr\[i\] < arr\[j\]) \{  
                        swap(arr,i,j);  
                    \}  
                \}  
            \}  
        \}  
    \}

/\*\*  
     \* 交换数组中的两个元素的位置  
     \* @param arr       // 数组  
     \* @param i         // 变量i  
     \* @param j         // 变量j  
     \*/  
    private static void swap(int\[\] arr, int i, int j) \{  
        int temp = arr\[i\];  
        arr\[i\] = arr\[j\];  
        arr\[j\] = temp;  
    \}

public static void main(String\[\] args) \{  
        int\[\] arr = \{1,3,2,5,9,10,53,33,55\};  
        System.out.println("排序数组：" + Arrays.toString(arr));  
        sort(arr,true);  
        System.out.println("升序排列：" + Arrays.toString(arr));  
        sort(arr,false);  
        System.out.println("降序排序：" + Arrays.toString(arr));  
    \}  
\}  
// 输出结果  
排序数组：\[1, 3, 2, 5, 9, 10, 53, 33, 55\]  
升序排列：\[1, 2, 3, 5, 9, 10, 33, 53, 55\]  
降序排序：\[55, 53, 33, 10, 9, 5, 3, 2, 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  
选择排序  
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列\[5， 5， 3\]第一次就将第一个\[5\]与\[3\]交换，导致第一个5挪动到第二个5后面）。

package com.wip.sorting;  
import java.util.Arrays;  
public class SelectSort \{

/\*\*  
     \* 选择排序  
     \* @param arr       排序的数组  
     \* @param asc       是否升序  
     \*/  
    public static void sort(int\[\] arr, boolean asc) \{  
        for (int i = 0; i < arr.length; i++) \{  
            int index = i;  
            for (int j = i + 1; j < arr.length; j++) \{  
                if (asc) \{  
                    if (arr\[index\] > arr\[j\]) \{ // 升序，选择无序区最小的元素  
                        index = j;  
                    \}  
                \} else \{  
                    if (arr\[index\] < arr\[j\]) \{// 降序，选择无序区最大的元素  
                        index = j;  
                    \}  
                \}  
            \}  
            if (index != i) \{  
                swap(arr,index,i);  
            \}  
        \}

public static void main(String\[\] args) \{  
        int\[\] arr = \{1,3,23,8,10,34,13,56\};  
        System.out.println("排序数组：" + Arrays.toString(arr));  
        sort(arr, true);  
        System.out.println("升序排列：" + Arrays.toString(arr));  
        sort(arr, false);  
        System.out.println("降序排列：" + Arrays.toString(arr));

\}  
\}

// 输出结果  
排序数组：\[1, 3, 23, 8, 10, 34, 13, 56\]  
升序排列：\[1, 3, 8, 10, 13, 23, 34, 56\]  
降序排列：\[56, 34, 23, 13, 10, 8, 3, 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  
56  
57  
插入排序  
插入排序(Insert Sort)将待排序的数组分为2部分：有序区，无序区。其核心思想是每次取出无序区中的第一个元素，插入到有序区中。 有序与无序区划分，就是通过一个变量标记当前数组中，前多少个元素已经是局部有序了。

package com.wip.sorting;  
import java.util.Arrays;  
public class InsertSort \{  
    /\*\*  
     \* 插入排序  
     \* @param arr       排序数组  
     \* @param asc       是否升序  
     \*/  
    public static void sort(int\[\] arr, boolean asc) \{  
        // 有序区最后一个元素位置  
        int orderedLastIndex = 0;//开始排序时，将有序区结束位置设为0 (开始位置总是0)，对应的无序区范围就是 1-arr.length  
        for (int i = orderedLastIndex + 1; i < arr.length; i++) \{//迭代无序区中的每一个元素，依次插入有序区中  
            int temp = arr\[i\];//记录无序区中的第一个元素值  
            int insertIndex = i;//在有序区中插入的索引的位置，刚开始就设置为自己的位置  
            for (int j = orderedLastIndex; j >= 0; j--) \{//从有序区从后往前开始比较  
                if (asc) \{//升序，有序区中比当前无序区中元素大的都右移一个位置  
                    if (arr\[j\] > temp) \{  
                        arr\[j+1\] = arr\[j\];  
                        insertIndex --;//有序区每移动一次，将插入位置-1  
                    \} else \{  
                        break;//有序区当前位置元素<=无序区第一个元素，那么之前的元素都会<=，不需要继续比较  
                    \}  
                \} else \{//降序，有序区中比当前无序区中元素小的都右移一个位置  
                    if (arr\[j\] < temp) \{  
                        arr\[j+1\] = arr\[j\];  
                        insertIndex --;  
                    \} else \{  
                        break;  
                    \}  
                \}  
            \}  
            arr\[insertIndex\] = temp;  
            orderedLastIndex ++;  
        \}  
    \}

public static void main(String\[\] args) \{  
        int\[\] arr = \{1,8,3,2,10,34,67,93,11\};  
        System.out.println("排序数组：" + Arrays.toString(arr));  
        sort(arr,true);  
        System.out.println("升序数组：" + Arrays.toString(arr));  
        sort(arr,false);  
        System.out.println("降序数组：" + Arrays.toString(arr));

\}  
\}

// 输出结果  
排序数组：\[1, 8, 3, 2, 10, 34, 67, 93, 11\]  
升序数组：\[1, 2, 3, 8, 10, 11, 34, 67, 93\]  
降序数组：\[93, 67, 34, 11, 10, 8, 3, 2, 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  
高级二分查找  
1.二分查找以称折半查找，优点是比较次数少，查找速度快，平均性能好。   
2.其缺点是要求待查表为有序表。   
3.二分查找的目的是查找元素索引，有个前提是数组元素必须为有序。

package com.wip.sorting;  
public class BinarySearch \{  
    /\*\*  
     \* 获取某个数在数组里出现在位置  
     \* @param arr       // 数组  
     \* @param num       // 要找的数  
     \* @return  
     \*/  
    public static int getIndex(int\[\] arr, int num) \{  
        int min = 0;  
        int max = arr.length - 1;  
        int mid = (min + max) /2;  
        System.out.println("min: " + min + " mid: " + mid + " max: " + max);

// 查找的算法  
        int index = -1; // 如果算到最后，index人值没有改变，代表num在arr中不存在

while (true) \{

if (arr\[mid\] == num) \{// 找到查找的数  
                index = mid;  
                break;  
            \}

if (arr\[mid\] > num) \{// num 在左边  
                max = mid - 1;  
                mid = (min + max) / 2;  
            \}

if (arr\[mid\] < num) \{// num 在右边  
                min = mid + 1;  
                mid = (min + max) / 2;  
            \}

if (min > max) \{ // 不符合逻辑  
                break;// 退出循环  
            \}  
        \}  
        return index;  
    \}

public static void main(String\[\] args) \{  
        int\[\] arr = \{11,22,33,89,34,66\};  
        int num = 33;  
        if (getIndex(arr, num) == -1) \{  
            System.out.println(num + " 在数组中不存在");  
        \} else \{  
            System.out.println(num + "索引位置: " + getIndex(arr, num)); //33索引位置: 2  
        \}  
    \}  
\}

\---------------------   
作者：KyrieCao   
来源：CSDN   
原文：https://blog.csdn.net/qq\_22067469/article/details/82149421   
版权声明：本文为博主原创文章，转载请附上博文链接！