亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全，請及時綁定郵箱和手機立即綁定

【Java數據結構與算法】第八章 快速排序、歸并排序和基數排序

第八章 快速排序、归并排序和基数排序
文章目录
第八章 快速排序、归并排序和基数排序
一、快速排序
1.基本介绍
2.代码实现
二、归并排序
1.基本介绍
2.代码实现
三、基数排序
1.基本介绍
2.代码实现
一、快速排序
1.基本介绍
快速排序（Quick Sort）是在冒泡排序基础上的递归分治法，其基本原理：选择一个关键值作为基准值。比基准值小的都在左边序列， 比基准值大的都在右边

当一个等于基准元素的元素在基准元素的右边时，由于小于等于基准元素的元素都要移动到基准元素左边，所以该元素和基准元素的相对位置就改变了，因此快速排序是一种不稳定的排序算法

算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

2.代码实现
package com.sisyphus.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**

  • @Description: 快速排序$

  • @Param: $

  • @return: $

  • @Author: Sisyphus

  • @Date: 7/17$
    */
    public class QuickSort {
    public static void main(String[] args) {
    //int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561};
    //quickSort(arr,0,arr.length -1);
    //System.out.println(Arrays.toString(arr));

     //创建一个 80000 个随机数的数组
 int[] arr = new int[80000];
 for (int i = 0; i < 80000; i++) {
     arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数
 }

 Date date1 = new Date();
 SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
 String data1Str = simpleDateFormat.format(date1);
 System.out.println("排序前的时间是：" + data1Str);

 quickSort(arr,0,arr.length - 1);

 Date date2 = new Date();
 String data2Str = simpleDateFormat.format(date2);
 System.out.println("排序后的时间是：" + data2Str);

    }

    /**
    *

    • @param arr 待处理的数组

    • @param left 最左边的下标

    • @param right 最右边的下标
      */
      public static void quickSort(int[] arr,int left, int right){
      int l =left;
      int r = right;
      int pivot = arr[(left + right) / 2];
      int temp = 0;//用于交换
      //while 循环的目的是让比 pivot 小的值放到左边，比 pivot 大的值放到右边
      while(l < r){
      //在 pivot 左边一直找，找到一个大于等于 pivot 的值才退出
      while (arr[l] < pivot){
      l += 1;
      }
      //在 pivot 右边一直找，找到一个小于等于 pivot 的值才退出
      while(arr[r] > pivot){
      r -= 1;
      }
      //如果 l >= r 说明 pivot 左右两边的值已经按照左边全是小于等于 pivot，右边全是大于等于 pivot 的规定排列好了
      if(l >= r){
      break;
      }
      //交换
      temp = arr[l];
      arr[l] = arr[r];
      arr[r] = temp;

       //如果交换完后，发现 arr[l] == pivot
 if (arr[l] == pivot){
     r -= 1;
 }
 //如果交换完后，发现 arr[r] == pivot
 if (arr[r] == pivot){
     l += 1;
 }

      }

      //如果 l == r,必须 l++,r–，否则会出现栈溢出
      if (l == r){
      l++;
      r–;
      }
      //向左递归
      if (left < r){
      quickSort(arr,left,r);
      }

      //向右递归
      if (right > l){
      quickSort(arr,l,right);
      }
      }
      }

二、归并排序
1.基本介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序

在交换过程中，2 个元素如果大小相等也没有任何操作交换，这不会破坏稳定性。合并过程中我们可以令相同的元素本来在前的还保持在前，这样就保证了相对顺序没有改变，因此归并排序也是稳定的排序算法

算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤 3 直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

2.代码实现
package com.sisyphus.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**

  • @Description: 归并排序$

  • @Param: $

  • @return: $

  • @Author: Sisyphus

  • @Date: 7/17$
    */
    public class MergeSort {
    public static void main(String[] args) {
    //int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
    //System.out.println(“归并排序后” + Arrays.toString(arr));

     //创建一个 80000 个随机数的数组
 int[] arr = new int[80000];
 for (int i = 0; i < 80000; i++) {
     arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数
 }

 Date date1 = new Date();
 SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
 String data1Str = simpleDateFormat.format(date1);
 System.out.println("排序前的时间是：" + data1Str);

 int temp[] = new int[arr.length];//归并排序需要一个额外空间
 mergeSort(arr, 0, arr.length - 1, temp);

 Date date2 = new Date();
 String data2Str = simpleDateFormat.format(date2);
 System.out.println("排序后的时间是：" + data2Str);

    }

    //分 + 合的方法
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
    if (left < right){
    int mid = (left + right) / 2;//中间索引
    //向左递归进行分解
    mergeSort(arr, left, mid, temp);
    //向右递归进行分解
    mergeSort(arr, mid+1,right,temp);
    //合并
    merge(arr, left, mid, right, temp);
    }
    }

    //合并的方法

    /**
    *

    • @param arr 排序的原始数组

    • @param left 左端有序序列的初始索引

    • @param mid 中间索引

    • @param right 右端索引

    • @param temp 做中转的数组
      */
      public static void merge(int[] arr, int left, int mid, int right, int[] temp){
      int i = left; //初始化 i，左端有序序列的初始索引
      int j = mid + 1;//初始化 j，右端有序序列的初始索引
      int t = 0; //指向 temp 数组的当前索引

      //（一）
      //先把左右两边（有序）的数据按照规则填充到 temp 数组
      //直到左右两边的有序序列有一边处理完毕
      while((i <= mid) && (j <= right)){
      //如果左边的有序序列的当前元素小于等于右边有序序列的当前元素
      //将左边的当前元素拷贝到 temp 数组
      //然后 t 后移，i 后移
      if (arr[i] <= arr[j]){
      temp[t] = arr[i];
      t++;
      i++;
      }else{//反之，将右边的当前元素拷贝到 temp 数组
      temp[t] = arr[j];
      t++;
      j++;
      }
      }

      //（二）
      //有剩余数据的一边，把其中的数据依次全部填充到 temp
      while(i <= mid){//左边的有序序列还有剩余的元素，就全部填充到 temp
      temp[t] = arr[i];
      t++;
      i++;
      }
      while(j <= right){//右边的有序序列还有剩余的元素，就全部填充到 temp
      temp[t] = arr[j];
      t++;
      j++;
      }

      //（三）
      //将 temp 数组的元素拷贝到 arr
      //注意：并不是每次都拷贝所有数据
      t = 0;
      int tempLeft = left;//
      //第一次合并时 tempLeft = 0，right = 1 第二次合并时 tempLeft = 2，right = 3 第三次合并时 tempLeft = 0，right = 3
      //最后一次 tempLeft = 0，right = 7

      三、基数排序
      1.基本介绍
      基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

點擊查看更多內容
為 TA 點贊

若覺得本文不錯，就分享一下吧！

評論

作者其他優質文章

正在加載中
  • 推薦
  • 評論
  • 收藏
  • 共同學習，寫下你的評論
感謝您的支持，我會繼續努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

 幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

 公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消