数组-简单排序

谁借莪１个温暖的怀抱￠ 2022-06-02 01:42 73阅读 0赞

#### **冒泡排序** ####

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

package ch02;
    public class BubbleSort {
         public static void sort(long[] arr) {
               long tmp = 0;
               for(int i = 0; i < arr.length - 1; i++) {
                    for(int j = arr.length - 1; j > i; j--) {
                         //如果后一位小于前一位，那么将两个数进行交换
                         if(arr[j] < arr[j - 1]) {
                               //进行交换
                               tmp = arr[j];
                               arr[j] = arr[j - 1];
                               arr[j - 1] = tmp;
                         }
                    }
               }
         }
    }

#### **选择排序：（交换的次数比冒泡排序少）** ####

简单选择排序的基本思想：给定数组：int\[\] arr=\{里面n个数据\}；第1趟排序，在待排序数据arr\[1\]~arr\[n\]中选出最小的数据，将它与arrr\[1\]交换；第2趟，在待排序数据arr\[2\]~arr\[n\]中选出最小的数据，将它与r\[2\]交换；以此类推，第i趟在待排序数据arr\[i\]~arr\[n\]中选出最小的数据，将它与r\[i\]交换，直到全部排序完成。

package ch02;
    public class SelectionSort {
         public static void sort(long[] arr) {
               int k = 0;//永远指向最小的值
               long tmp = 0;
               for(int i = 0; i < arr.length - 1; i++) {
                    k = i;
                    for(int j = i; j < arr.length; j++) {
                         if(arr[j] < arr[k]) {
                               k = j;
                         }
                    }
                    //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
                    tmp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = tmp;
               }
         }
    }

#### **插入排序** ####

在将元素插入到有序队列中，要将这个元素与有序队列的元素依次比较，如果小于有序队列的某个元素，将其插入到该元素的前面，否则不做操作。依次比较完毕，没有比其大的，就将其放在有序队列的末尾。  
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是Θ(n2)。  
编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。

package ch02;
    public class InsertSort {
         public static void sort(long[] arr) {
               long tmp = 0;
               for(int i = 1; i < arr.length; i++) {
                    tmp = arr[i];
                    int j = i;
                    while(j > 0 && arr[j-1] >= tmp) {
                         arr[j] = arr[j - 1];
                         j--;
                    }
                    arr[j] = tmp;
               }
         }
         public static void main(String[] args) {
               long[] arr = new long[5];
               arr[0] = 2;
               arr[1] = 34;
               arr[2] = 23;
               arr[3] = 1;
               arr[4] = -4;
               System.out.print("[");
               for(long num : arr) {
                    System.out.print(num + " ");
               }
               System.out.print("]");
               System.out.println(); 
               sort(arr); 
               System.out.print("[");
               for(long num : arr) {
                    System.out.print(num + " ");
               }
               System.out.print("]");
               System.out.println(); 
         }
    }