Java中常见的排序算法

Java中常见的排序算法

尼采
2021-10-04 / 0 评论 / 190 阅读 / 正在检测是否收录...

常见算法可以分为两大类:
  非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。
  线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。

1、冒泡排序
思路:外层循环从1到n-1,内循环从当前外层的元素的下一个位置开始,依次和外层的元素比较,出现逆序就交换,通过与相邻元素的比较和交换来把小的数交换到最前面。

 //定义一个数组
        int[] arr = new int[]{3, 1, 2, 9, 8, 6, 7, 4, 45, 69, 18, 66, 16};
        //冒泡排序
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) { //-j的意思是每次排完一次都确定了最后一个,所以最后的就不用在比了
                if (arr[i] > arr[i + 1]) {  //如果第一位大于第二位
                    int t = arr[i];   //定义一个变量,将第一位的值给这个变量,那么现在第一位也就空了
                    arr[i] = arr[i + 1]; //将第二位的值放到第一位,此时,第二位也就空了
                    arr[i + 1] = t;   //此时再将临时变量里面的值放到第二位
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

2、选择排序
思路:冒泡排序是通过相邻的比较和交换,每次找个最小值。选择排序是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

  //定义一个数组
        int[] arr = {49, 38, 65, 97, 76, 13, 27, 50};
        //选择排序
        for (int i = 0; i < arr.length-1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

3、插入排序
思路:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。可以理解为玩扑克牌时的理牌;

 private static void sort(int[] array) {
        int n = array.length;
      /**
     *从第二位数字开始,每一个数字都试图跟它的前一个比较并交换,并重复;直到前一个数字不存在或者比它小或相等时停下来
     **/
         for (int i = 1; i < n; i++) {//从第二个数开始
             int key = array[i];
             int j = i -1;
             while (j >= 0 && array[j]>key) {
                 array[j + 1] = array[j];     //交换
                j--;                                //下标向前移动
             }
             array[j+1] = key;
         }
     }

0

评论 (0)

取消