排序算法Java实现

会通过Java语言实现:冒泡排序,插入排序,选择排序,归并排序,快速排序,桶排序,计数排序,基数排序,希尔排序 1.1 执行效率

本文会通过Java语言实现:冒泡排序,插入排序,选择排序,归并排序,快速排序,桶排序,计数排序,基数排序,希尔排序

1 分析排序算法1.1 执行效率

最好的情况,最坏的情况,平均情况时间复杂度

时间复杂度的系数,常数,低阶

比较次数和交换次数

1.2 算法的内存消耗

算法的内存消耗我们可以通过空间复杂度来度量。

原地排序算法,就是特指空间复杂度是O(1)的排序算法。

1.3 排序算法的稳定性

如果序列中有值相等的元素, 经过排序之后,相等元素之间原有的先后顺序不变化。

2 冒泡排序

稳定排序算法,原地排序算法,时间复杂度:O(n^2)

冒泡排序操作相邻的两个数据,每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系。每次冒泡都能选出最大的或者最小的值。

[Java] 纯文本查看 复制代码

?

/**

  • 冒泡排序
  • @param arr
  • @return

*/

public static int[] bubbleSort(int[] arr) {

if (arr == null || arr.length == 0) {
     return null;
 }
 int n = arr.length;
 // 总共需要循环n次  每次通过冒泡 得到最大的
 for (int i = 0; i < n; i++) {
     // 因为上一次已经确定了最大的,所以需要遍历的数据就是(n-1)-i
     boolean flag = true;
     for (int j = 0; j < (n - 1) - i ; j++) {
         if (arr[j] > arr[j + 1]) {
             int temp = arr[j];
             arr[j] = arr[j + 1];
             arr[j + 1] = temp;
             flag = false;
         }
     }
     // 因为冒泡 如果这次冒泡没有数据没有交换所以数据已经有序了,可以提前退出
     if (flag) {
         break;
     }
 }
 return arr;

}

3 插入排序

稳定排序算法,原地排序算法,时间复杂度O(n^2)

根据,把位置的元素,插入在有序的集合中,插入的时候根据元素位置大小。

首先:讲数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素就是数组的第一个元素。

[Java] 纯文本查看 复制代码

?

/**

* 插入排序
 * @param arr
 * @return
 */
public static int [] insertSort(int [] arr){
    if (arr==null||arr.length==0) {
        return null;
    }
    int n = arr.length;
    // n从一1开始表示a[0]属于有序序列
    for (int i = 1; i < n; i++) {
        // 当前需要比较的数字
        int value = arr[i];
        // 需要比较的次数
        int j = i-1;
        // 查找插入的位置
        for (; j>=0; j--) {
            if (arr[j]>value) {
                // 数据移动
                arr[j+1] = arr[j];
            }else {
                // 插入排序前面是有序序列,所有不需要移动数据的时候,直接跳出比较下个数字
                break;
            }
        }
        // 插入数据
        arr[j+1] = value;
    }
    return arr;
}

4 选择排序

不是稳定排序算法,原地排序算法,时间复杂度是O(n^2)

每次会从未排序区间中找到最小元素,将其放到已排序区间的末尾

[Java] 纯文本查看 复制代码

?

/**

  • 选择排序
  • @param arr
  • @return

*/

public static int [] selectionSort(int [] arr){

if (arr==null||arr.length==0) {
      return null;
  }
  int n = arr.length;
  int temp = 0;
  int minKey = 0;
  // 刚开始没有有序区间,所以从0开始
  for (int i = 0; i < n; i++) {
      minKey = i;
      // 寻找无序区间最小的元素
      for (int j = i+1; j < n; j++) {
          if (arr[j]<arr[minKey]) {
              minKey = j;
          }
      }
      // 交换位置   
      temp = arr[i];
      arr[i] = arr[minKey];
      arr[minKey] = temp;
  }
  return arr;

原文 

https://segmentfault.com/a/1190000021040432

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 排序算法Java实现

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址