栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序算法 数据结构

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序算法 数据结构

一、直接插入排序

    int[] insertSort(int[] arr) {
        int temp, i, j;
        int n = arr.length;
        for (i = 1; i < n; i++) {
            temp = arr[i];//从第二个元素开始,与前面的元素比较,如果比前面的大,就不用动,
            // 小则将前面的放到temp的位置,temp继续与前面的比较
            j = i - 1;
            while (j >= 0 && temp < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        return arr;
    }

排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。

二、希尔排序

 int[] shellSort(int[] arr) {
        int i, j, n, gap, temp;
        n = arr.length;
        for (gap = n / 2; gap > 0; gap /= 2) {
            for (i = gap; i < n; i++) {                   //-----------------+-----------+
                temp = arr[i];                                           //  |           
                for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) { //  |  此范围   
                    arr[j] = arr[j - gap];                               //  |  相当于   
                }                                                        //  |  插入排序  
                arr[j] = temp;                                           //  |            
            }             //-------------------------------------------------+-----------+
        }
        return arr;
    }

排序过程:先取一个正整数d1

 三、简单选择排序

     
    int[] easilySelectSort(int[] arr) {
        int temp, i, j, k, n;
        n = arr.length;
        temp = arr[0];
        for (i = 0; i < n; i++) {
            k = i;
            for (j = i + 1; j < n; j++) {
                if (arr[k] > arr[j]) {
                    k = j;
                    temp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = temp;
                }
            }
        }
        return arr;
    }

排序过程 :首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换 重复上述操作,共进行n-1趟排序后,排序结束

 四、堆排序

    static int[] heapSort(int[] arr) {
        int i, n, temp;
        n = arr.length;
        //建堆操作,做出一个大顶堆
        for (i = n / 2 - 1; i >= 0; i--)
            adjust(arr, i, n - 1);
        //排序操作,对大顶堆操作
        for (i = n - 1; i > 0; i--) {
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjust(arr, 0, i - 1);
        }
        return arr;
    }

    //调整函数,负责构建大顶堆,将大的节点往上挪
    static void adjust(int[] arr2, int low, int height) {
        int i = low, j = i * 2 + 1;//j是i的左节点
        int temp = arr2[i];
        while (j <= height) {
            if (j < height && arr2[j] < arr2[j + 1])
                j++;
            if (temp < arr2[j]) {
                arr2[i] = arr2[j];
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
        arr2[i] = temp;
    }

 五、冒泡排序

    static int[] bubbleSort(int[] arr) {
        int i, j, n, temp;
        n = arr.length;
        for (i = n - 1; i > 0; i--) {
            for (j = 1; j <= i; j++) {
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    j++;
                }
            }
        }
        return arr;
    }

排序过程: 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r[1].key>r[2].key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止

六、快速排序

    static int[] quicklySort(int[] arr, int low, int height) {
        int i, j, temp;
        i = low;
        j = height;
        if (low < height) {
            temp = arr[low];
            while (i < j) {
                while (j > i && arr[j] >= temp) j--;
                if (j > i) {
                    arr[i] = arr[j];
                    i++;
                }
                while (i < j && arr[i] < temp) i++;
                if (i < j) {
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = temp;
            quicklySort(arr, low, i - 1);
            quicklySort(arr, i + 1, height);
        }
        return arr;
    }

 

 七、归并排序

 
    static int[] mergeSort(int[] arr, int low, int height) {
        if (low < height) {
            int mid = (low + height) / 2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, height);
            merge(arr, low, mid, height);
        }
        return arr;
    }

    static void merge(int[] arr, int low, int mid, int height) {
        int i, j, k;
        int n1 = mid - low + 1;
        int n2 = height - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (i = 0; i < n1; i++)
            L[i] = arr[low + i];
        for (j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        i = 0;
        j = 0;
        k = low;
        while (i < n1 && j < n2) {
            if (L[i] < R[j]) {
                arr[k] = L[i++];
            } else {
                arr[k] = R[j++];
            }
            k++;
        }
        while (i < n1)
            arr[k++] = L[i++];
        while (i < n2)
            arr[k++] = R[j++];
    }

排序过程 :设初始序列含有n个记录,则可看成n个有序的子序列,每个子序列长度为1 两两合并,得到n/2个长度为2或1的有序子序列 再两两合并,……如此重复,直至得到一个长度为n的有序序列为止


 总结:

若待排序记录的个数n较小(<=50)时,可以采用简单排序方法,其中以直接插入排序最简单;

若n较大时,则应采用归并、快速或堆排序,其中归并排序满足稳定性的要求,可以和直接插入排序结合使用,即先利用插入排序得到多个长度小于50的有序子表,然后进行多趟归并。

若待排序记录已按排序码基本有序,应采用直接插入排序或冒泡排序;

以下是上述代码的测试结果:

 public static void main(String[] args) {
        int[] arr = {3, 6, 4, 8, 0, 3, 4, 5, 77, 3, 45, 6, 8, 88, 9, 2435, -765, 0, -9};
        System.out.print("排序前的数组: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("直接插入排序: ");
        int[] arr01 = insertSort(arr);
        for (int i : arr01) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("简单选择排序: ");
        int[] arr02 = easilySelectSort(arr);
        for (int i : arr02) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("冒泡排序: ");
        int[] arr03 = bubbleSort(arr);
        for (int i : arr03) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("希尔排序: ");
        int[] arr04 = shellSort(arr);
        for (int i : arr04) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("快速排序: ");
        int[] arr05 = quicklySort(arr, 0, arr.length - 1);
        for (int i : arr05) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("堆排序: ");
        int[] arr06 = heapSort(arr);
        for (int i : arr06) {
            System.out.print(i + " ");
        }

        System.out.println();
        System.out.print("归并排序: ");
        int[] arr07 = mergeSort(arr, 0, arr.length - 1);
        for (int i : arr07) {
            System.out.print(i + " ");
        }

    }

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/935833.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号