排序算法(1)-冒泡排序,选择排序,插入排序,希尔排序,快速排序

柔光的暖阳◎ 2022-05-23 09:07 310阅读 0赞

一些基本的排序算法:

  1. package tenSortingMethods;
  2. /** * @author zhangdi * @description 排序算法 * @Date 20180531 */
  3. public class Sort { 
  5.     public static void main(String[] args) {
  6.         int[] arr = {
  7.    6,1,2,7,9,3,4,5,10,8};//{ 26, 88, 45, 57, 12, 31, 12, 2, 64, 32, 20, 99, 1 };
  8.         int[] arr1 = { 2, 1, 3, 5, 4 };// {6,1,2,7,9,3,4,5,10,8};
  10.         // System.out.println(arr.getClass());
  11.         System.out.println(" arr before sorting: " + IntArrtoString(arr));
  12.         // BubbleSort(arr);
  13.         // BubbleSort2(arr);
  14.         // BubbleSort1_better(arr);
  15.         // SelectSort(arr);
  16.         // InsertionSort(arr);
  17.         // ShellSort(arr);
  18.         // ShellSort2(arr);
  20.         // int[] quickSort = new Sort().QuickSort(arr, 0, arr.length - 1);
  21.         // System.out.println(" quickSort after sorting: " +
  22.         // IntArrtoString(quickSort));
  25.          int[] quickSort2 = new Sort().QuickSort2(arr, 0, 9);
  26.         // System.out.println(" quickSort2 after sorting: " +
  27.         // IntArrtoString(quickSort2));
  29.          System.out.println(" arr after sorting: " + IntArrtoString(arr));
  31.     }
  33.     /** * @description 冒泡排序 * @param arr * @description : 两两比较,大的往后放; 每一次比较完成之后,下一次就少比较一个元素 * 第一次比较有0个元素不比较;第二次有一个元素不需要比较;第三次有两个元素不需要比较; * 共需要比较arr.length-1次 */
  34.     public static void BubbleSort(int[] arr) {
  36.         int temp;// 临时变量
  37.         if (arr == null || arr.length == 0)
  38.             return;
  39.         for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。
  40.             for (int j = arr.length - 1; j > i; j--) {
  42.                 if (arr[j] < arr[j - 1]) {
  43.                     temp = arr[j];
  44.                     arr[j] = arr[j - 1];
  45.                     arr[j - 1] = temp;
  46.                 }
  47.             }
  48.         }
  49.     }
  51.     /** * @description 冒泡排序-2 * @param arr * */
  52.     public static void BubbleSort2(int[] arr) {
  54.         int temp;// 临时变量
  55.         if (arr == null || arr.length == 0)
  56.             return;
  57.         for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。
  58.             for (int j = 0; j < arr.length - 1 - i; j++) {
  60.                 if (arr[j] > arr[j + 1]) {
  61.                     temp = arr[j];
  62.                     arr[j] = arr[j + 1];
  63.                     arr[j + 1] = temp;
  64.                 }
  65.             }
  66.         }
  67.     }
  69.     /** * @description 冒泡排序-1-优化 * @param arr * * 针对问题:数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。 * 方案: 设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 * 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。 * */
  70.     public static void BubbleSort1_better(int[] arr) {
  72.         int temp;// 临时变量
  73.         boolean flag;
  74.         if (arr == null || arr.length == 0)
  75.             return;
  76.         for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。
  77.             flag = false;
  78.             for (int j = arr.length - 1; j > i; j--) {
  79.                 if (arr[j] < arr[j - 1]) {
  80.                     temp = arr[j];
  81.                     arr[j] = arr[j - 1];
  82.                     arr[j - 1] = temp;
  83.                 }
  84.             }
  85.             if (!flag)
  86.                 break;
  87.         }
  88.     }
  90.     /** * @description 选择排序 * @param arr * 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换； * 第二次遍历n-2个数，找到最小的数值与第二个元素交换； 。。。 * 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。 */
  91.     public static void SelectSort(int[] arr) {
  92.         int len = arr.length;
  93.         int temp;// 临时变量
  94.         if (arr == null || len == 0)
  95.             return;
  96.         for (int i = 0; i < len - 1; i++) {
  97.             int minIndex = i;// 假定此时i位置元素为最小数值
  98.             for (int j = i + 1; j < arr.length; j++) {
  99.                 if (arr[j] < arr[minIndex]) {
  100.                     // 如果i+1后的元素值小于i位置的元素,那么改变minIndex值.当内层循环走完,此时数组最小值得小标就确定了
  101.                     minIndex = j;
  102.                 }
  103.             }
  104.             if (minIndex != i) {
  105.                 // 最小值下标改变,交换元素
  106.                 temp = arr[i];
  107.                 arr[i] = arr[minIndex];
  108.                 arr[minIndex] = temp;
  109.             }
  110.         }
  111.     }
  113.     /** * @description 插入排序 * @param arr * @description : 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。 * 如此反复循环，直到全部排好顺序。 位于表中后面的元素依次与表中前面的元素比较，若比之小，则还需继续和更前面的元素比较， * 直至遇到一个比它大的元素或者比较到第一个元素(哨兵)了。 */
  114.     public static void InsertionSort(int[] arr) {
  115.         int len = arr.length;
  116.         int temp;// 临时变量
  117.         if (arr == null || len == 0)
  118.             return;
  119.         for (int i = 0; i < len - 1; i++) {
  120.    // 趟数n-1趟
  121.             for (int j = i + 1; j > 0; j--) {
  122.                 if (arr[j] < arr[j - 1]) {
  123.                     temp = arr[j];
  124.                     arr[j] = arr[j - 1];
  125.                     arr[j - 1] = temp;
  126.                 } else {
  127.                     break;
  128.                 }
  129.             }
  130.         }
  131.     }
  133.     /** * @description 希尔排序 (最小增量排序) * @param arr * @description: 我们选择增量gap=length/2，缩小增量继续以gap = * gap/2的方式，这种增量选择我们可以用一个序列来表示，{n /2,(n/2)/2...1}，称为增量序列。 * 希尔排序的增量序列的选择与证明是个数学难题， 我们选择的这个增量序列是比较常用的，也是希尔建议的增量， * 称为希尔增量，但其实这个增量序列不是最优的。 此处我们做示例使用希尔增量。 * 比如原始数组8917235460,初始增量为gap =length/5;即数组被分为五组 * [8,3],[9,5],[1,4],[7,6],[2,0] ,对五组分别进行插入排序;第一次排序后: * 3514089472,缩小增量为gap =gap/2 = * 2;分为两组[3,5,1,4,0],[8,9,4,7,2],插入排序 -->[0214357698], * 再缩小增量gap = gap/ = 1,[0214357698] -->插入排序. * * */
  134.     public static void ShellSort(int[] array) {
  135.         int temp = 0;
  136.         int incre = array.length;
  137.         while (true) {
  138.             incre = incre / 2;
  139.             for (int k = 0; k < incre; k++) { // 根据增量分为若干子序列
  140.                 for (int i = k + incre; i < array.length; i += incre) {
  141.                     for (int j = i; j > k; j -= incre) {
  142.                         if (array[j] < array[j - incre]) {
  143.                             temp = array[j - incre];
  144.                             array[j - incre] = array[j];
  145.                             array[j] = temp;
  146.                         } else {
  147.                             break;
  148.                         }
  149.                     }
  150.                 }
  151.             }
  153.             if (incre == 1) {
  154.                 break;
  155.             }
  156.         }
  157.     }
  159.     /** * @description 希尔排序 (最小增量排序) * @param arr * 在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中， * 我们可以不用这么按部就班地处理完一组再调转回来处理下一组（ 这样还得加个for循环去处理分组）比如[5,4,3,2,1,0] * ，首次增量设gap=length/2=3,则为3组[5,2] [4,1] * [3,0]，实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时， * 可以采用元素交换法寻找最终位置， 也可以采用数组元素移动法寻觅。 * */
  160.     /** * 希尔排序 针对有序序列在插入时采用交换法 见图 * * @param arr */
  161.     public static void ShellSort2(int[] arr) {
  162.         System.out.println("ShellSort2 start.........");
  163.         // 增量gap，并逐步缩小增量
  164.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  165.             // 从第gap个元素，逐个对其所在组进行直接插入排序操作
  166.             System.out.println("1 gap:" + gap + " arr:" + IntArrtoString(arr));
  167.             for (int i = gap; i < arr.length; i++) {
  169.                 int j = i;
  170.                 while (j - gap >= 0 && arr[j] < arr[j - gap]) {
  171.                     // 插入排序采用交换法
  172.                     swap(arr, j, j - gap);
  173.                     j -= gap;
  174.                 }
  175.                 System.out.println("2 gap:" + gap + " i:" + i + " arr:" + IntArrtoString(arr));
  176.             }
  177.         }
  178.         System.out.println("ShellSort2 end...........");
  179.     }
  181.     /** * 希尔排序 针对有序序列在插入时采用移动法。 * * @param arr */
  182.     public static void ShellSort3(int[] arr) {
  183.         // 增量gap，并逐步缩小增量
  184.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  185.             // 从第gap个元素，逐个对其所在组进行直接插入排序操作
  186.             for (int i = gap; i < arr.length; i++) {
  187.                 int j = i;
  188.                 int temp = arr[j];
  189.                 if (arr[j] < arr[j - gap]) {
  190.                     while (j - gap >= 0 && temp < arr[j - gap]) {
  191.                         // 移动法
  192.                         arr[j] = arr[j - gap];
  193.                         j -= gap;
  194.                     }
  195.                     arr[j] = temp;
  196.                 }
  197.             }
  198.         }
  199.     }
  201.     /** * 交换数组元素 * * @param arr * @param a * @param b */
  202.     public static void swap(int[] arr, int a, int b) {
  203.         arr[a] = arr[a] + arr[b];
  204.         arr[b] = arr[a] - arr[b];
  205.         arr[a] = arr[a] - arr[b];
  206.     }
  208.     /** * @param arr * @description 快速排序 基本思想：（分治） 先从数列中取出一个数作为key值； * 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边； 对左右两个小数列重复第二步，直至各区间只有1个数。 * @ses http://developer.51cto.com/art/201403/430986.htm * https://blog.csdn.net/morewindows/article/details/6684558 */
  209.     // 快速排序
  210.     public int[] QuickSort(int[] a, int l, int r) {
  212.         if (l < r) {
  213.             int i = l, j = r, v = a[l];// i:左边开始活动坐标，j:右边开始活动坐标，v：基数，用于对比的值，一般取第一个
  214.             while (i < j) {
  215.    // 只要左边游标和游标不重叠的话那么就继续遍历
  216.                 System.out.println("i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  217.                 // 每一轮遍历的时候只进行一轮，把右边的一个比基数小的数移动到左边，把左边比基数大的数移动到右边
  218.                 while (i < j && a[j] > v)
  219.                     // 找出右边比左边小的坐标
  220.                     j--;
  221.                 if (i < j)
  222.                     a[i++] = a[j];// 进行移动，左边坐标移动一个数
  223.                 System.out.println("i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  224.                 while (i < j && a[i] < v)
  225.                     // 找出左边比右边大的坐标
  226.                     i++;
  227.                 if (i < j)
  228.                     a[j--] = a[i];// 进行移动，右边坐标移动一个数
  229.                 System.out.println("i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  230.             }
  231.             a[i] = v;// 当游标重叠时填入基数
  232.             this.QuickSort(a, l, i - 1);
  233.             this.QuickSort(a, i + 1, r);
  234.             return a;
  235.         }
  236.         return a;
  237.     }
  239.     /** * @param a * @param left * @param right * @return QuickSort2在一轮对比基准数的过程中不移动基准数,减少移动次数 */
  240.     public int[] QuickSort2(int[] a, int left, int right) {
  241.         //校验要初始化变量之前;不校验易报错:java.lang.ArrayIndexOutOfBoundsException
  242.         if (left>right ) {
  243.             return a;
  244.         }
  245.         int i = left, j = right, s = a[left];
  246.         int temp;
  248.         while (i < j) {
  249.             //System.out.println("1--------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  250.             while (a[j] >= s && j > i) {
  251.                 j--;
  252.                 //System.out.println("2--------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  253.             }
  254.             while (a[i] <= s && j > i) {
  255.                 i++;
  256.                 //System.out.println("3--------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  257.             }
  258.             if (i < j) {
  259.                 temp = a[j];
  260.                 a[j] = a[i];
  261.                 a[i] = temp;
  262.                 //System.out.println("4---------i:" + i + " j:" + j + " arr:" + IntArrtoString(a));
  263.             }
  264.         }
  265.         a[left] = a[i];
  266.         a[i] = s;
  268.         QuickSort2(a, left, i - 1);
  269.         QuickSort2(a, i + 1, right);
  270.         return a;
  272.     }
  276. }

发表评论

表情：
评论列表 （有 0 条评论，310人围观）

还没有评论，来说两句吧...

相关阅读