Java实现8种排序算法的示例代码

冒泡排序 O(n2)

两个数比较大小,较大的数下沉,较小的数冒起来。

public static void bubbleSort(int[] a) {
    //临时变量
    int temp;
    //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次
    for (int i = 0; i < a.length; i++) {
      //从最后向前面两两对比,j是比较中下标大的值
      for (int j = a.length - 1; j > i; j--) {
        //让小的数字排在前面
        if (a[j] < a[j - 1]) {
          temp = a[j];
          a[j] = a[j - 1];
          a[j - 1] = temp;
        }
      }
    }
  }

选择排序 O(n2)

在长度为N的无序数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换;
第二次遍历n-2个数,找到最小的数值与第二个元素交换;
。。。
第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成。

public static void selectSort(int[] a) {
    //临时变量
    int temp;
    //i是循环次数,也是选择交换的结果的位置下标,5个数组循环5次
    for (int i = 0; i < a.length; i++) {
      //最小值下标
      int min = i;
      for (int j = i + 1; j < a.length; j++) {
        if (a[min] > a[j]) {
          min = j;
        }
      }
      temp = a[i];
      a[i] = a[min];
      a[min] = temp;
    }
  }

插入排序 O(n2)

在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

public static void insertSort(int[] a) {
    int temp;
    //i是循环次数,也是插入的队列的长度,最后一位是a[i]
    //所以一开始a[0]是排好的一个队列,比较a.length-1次,最后一次循环是a[a.length-1]插入a[0]~a[a.length-2]
    for (int i = 0; i < a.length - 1; i++) {
      //a[j]是要插入的数字,从a[j]往a[0]比较
      for (int j = i + 1; j > 0; j--) {
        //如果插入的数小,交换位置
        if (a[j] < a[j - 1]) {
          temp = a[j];
          a[j] = a[j - 1];
          a[j - 1] = temp;
        } else {
          //因为默认a[0]~a[i]是排好的,a[i+1]比a[i]大的话,就不用比较后面了
          break;
        }
      }
    }
  }

希尔排序 O(n1.5)

在要排序的一组数中,根据某一增量分为若干子序列,并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

public static void shellSort(int[] a) {
    int temp;
    int d = a.length;
    for (; ; ) {
      d = d / 2;
      //根据差值分组为子序列
      for (int k = 0; k < d; k++) {
        //此时对每组数列进行插入排序,数组为a[k+d],a[k+2d]...a[k+n*d]
        for (int i = k + d; i < a.length; i += d) {
          // a[j]是要插入的数字,从a[j]往a[0]比较,跨度为d
          for (int j = i; j > k; j -= d) {
            //如果插入的数小,交换位置
            if (a[j] < a[j - d]) {
              temp = a[j];
              a[j] = a[j - d];
              a[j - d] = temp;
            } else {
              //因为默认a[0]~a[i]是排好的,a[i+1]比a[i]大的话,就不用比较后面了
              break;
            }
          }
        }
      }
      if (d == 1) {
        break;
      }
    }
  }

快速排序 O(N*logN)

先从数列中取出一个数作为base值;
将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
对左右两个小数列重复第二步,直至各区间只有1个数。

public void quickSort(int a[], int l, int r) {
    //左边必须大于右边
    if (l >= r) {
      return;
    }
    int i = l;
    int j = r;
    //选择第一个数为基准
    int base = a[l];
    while (i < j) {
      //从右向左找第一个小于base的值,如果大于左移一位,直到找到小值或者i/j重合
      while (i < j && a[j] > base) {
        j--;
      }
      //从左向右找第一个大于base的值,如果小于右移一位,直到找到大值或者i/j重合
      while (i < j && a[i] < base) {
        i++;
      }
      //交换
      if (i < j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
      }
    }
    //将基准值放到i右移到的位置
    a[i] = base;
    //将i左边和i右边分别排序
    quickSort(a, l, i - 1);//递归调用
    quickSort(a, i + 1, r);//递归调用
  }

归并排序 O(N*logN)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。
这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。
然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

private static void mergeSort(int[] a, int first, int last, int temp[]) {
    if (first < last) {
      //中间值
      int middle = (first + last) / 2;
      //左半部分排序
      mergeSort(a, first, middle, temp);
      //右半部分排序
      mergeSort(a, middle + 1, last, temp);
      //合并左右部分
      mergeArray(a, first, middle, last, temp);
    }
  }

  private static void mergeArray(int a[], int first, int middle, int end, int temp[]) {
    int i = first;
    int m = middle;
    int j = middle + 1;
    int n = end;
    int k = 0;
    while (i <= m && j <= n) {
      if (a[i] <= a[j]) {
        temp[k] = a[i];
        k++;
        i++;
      } else {
        temp[k] = a[j];
        k++;
        j++;
      }
    }
    while (i <= m) {
      temp[k] = a[i];
      k++;
      i++;
    }
    while (j <= n) {
      temp[k] = a[j];
      k++;
      j++;
    }
    for (int r = 0; r < k; r++) {
      a[first + r] = temp[r];
    }
  }

堆排序 O(N*logN)

利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

public static void heapSort(int a[]) {
    //堆顶最大值和数组最后(叶节点)交换 长度-1 次
    for (int i = a.length - 1; i > 0; i--) {
      //构建大顶堆(最大堆)
      buildHeap(a, i);
      //堆顶最大值和数组最后(叶节点)交换
      swap(a, 0, i);
    }
  }

  //构建大顶堆(最大堆)
  public static void buildHeap(int a[], int lastIndex) {
    //排最后的非叶节点为 长度/2-1,从第i检查到堆顶第0项,上浮大值
    for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
      //必定存在的左叶节点,不一定存在的右叶节点
      int left = i * 2 + 1;
      int right = i * 2 + 2;
      //max为左右叶节点中的最大值
      int max = left;
      if (right <= lastIndex) {
        if (a[left] < a[right]) {
          max = right;
        }
      }
      //上浮大值
      if (a[i] < a[max]) {
        swap(a, i, max);
      }
    }
  }

  //交换值
  public static void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

基数排序 O(d(n+r))

【d代表关键字有d位,n代表n个记录,r代表r个空队列】
基数排序(radix sort),相对于常见的比较排序,基数排序是一种分配式排序,即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。

public static void radixSort(int[] a) {
    //位数
    int digit = 1;
    //作为排序后数组的新下标
    int newIndex = 0;
    //供基数排序使用的二维数组,第一维度固定10位0~9,第二维度根据下标依次存放每次基数排序的结果
    int[][] container = new int[10][a.length];
    //第一维度每个数组的内容计数,最少为10,防止数组全是个位数时越界,例如五位数组最大值为8,counter.length=5 ,counter[8]就越界
    int counterLength = 10;
    if (a.length > 10) {
      counterLength = a.length;
    }
    int[] counter = new int[counterLength];
    //算出数组中最大的值,用来确定最大位
    int max = a[0];
    int maxDigit = 0;
    for (int i = 0; i < a.length; i++) {
      if (a[i] > max) {
        max = a[i];
      }
    }
    while (max > 0) {
      max /= 10;
      maxDigit++;
    }
    //对每位进行排序
    while (digit <= maxDigit) {
      //对每个数值该位取余,container[remainder],并计数该位置上数值的下标counter[remainder]
      for (int num : a) {
        int remainder = (num / digit) % 10;
        container[remainder][counter[remainder]] = num;
        counter[remainder]++;
      }
      //将上一步放入容器的数值依次覆盖到远数组中
      for (int i = 0; i < 10; i++) {
        for (int j = 0; j < counter[i]; j++) {
          a[newIndex] = container[i][j];
          newIndex++;
        }
        counter[i] = 0;
      }
      digit *= 10;
      newIndex = 0;
    }
  }

以上就是Java实现8种排序算法的示例代码的详细内容,更多关于Java实现8种排序算法的资料请关注我们其它相关文章!

时间: 2020-06-10

JAVA用递归实现全排列算法的示例代码

求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i

C++实现顺序排序算法简单示例代码

本文实例讲述了最直接的顺序排序法VC++示例代码,还记得以前上学时候这是计算机的必考题,而且在排序算法中,顺序排序似乎是最简单的了,也是最容易掌握的.现在列出来让大家重新回顾一下! 具体代码如下: //顺序排序 void InsertSort(int r[], int n){ for (int i=2; i<n; i++){ r[0]=r[i]; //设置哨兵 for (int j=i-1; r[0]<r[j]; j--) //寻找插入位置 r[j+1]=r[j]; //记录后移 r[j+1]

java实现的各种排序算法代码示例

折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

Java语言字典序排序算法解析及代码示例

字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

C#几种排序算法

作者:Sabine [导读]本文介绍了C#的四种排序算法:冒泡排序.选择排序.插入排序和希尔排序 冒泡排序 using System: namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp: bool done=false: j=1: while((j<list.Length)&&(!done)) { done=true: for(i=0:i&

Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }

PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<

Java使用sftp定时下载文件的示例代码

sftp简介 sftp是Secure File Transfer Protocol的缩写,安全文件传送协议.可以为传输文件提供一种安全的网络的加密方法.sftp 与 ftp 有着几乎一样的语法和功能.SFTP 为 SSH的其中一部分,是一种传输档案至 Blogger 伺服器的安全方式.其实在SSH软件包中,已经包含了一个叫作SFTP(Secure File Transfer Protocol)的安全文件信息传输子系统,SFTP本身没有单独的守护进程,它必须使用sshd守护进程(端口号默认是22)

Java多线程文件分片下载实现的示例代码

多线程下载介绍 多线程下载技术是很常见的一种下载方案,这种方式充分利用了多线程的优势,在同一时间段内通过多个线程发起下载请求,将需要下载的数据分割成多个部分,每一个线程只负责下载其中一个部分,然后将下载后的数据组装成完整的数据文件,这样便大大加快了下载效率.常见的下载器,迅雷,QQ旋风等都采用了这种技术. 分片下载 所谓分片下载就是要利用多线程的优势,将要下载的文件一块一块的分配到各个线程中去下载,这样就极大的提高了下载速度. 技术难点 并不能说是什么难点,只能说没接触过不知道罢了. 1.如何请