Java——排序算法

╰+哭是因爲堅強的太久メ 2024-04-19 07:04 0阅读 0赞

# 一、概述 #

排序是数据处理中一种很重要也很常用的运算。就是将一组对象按照规定的次序重新排列的过程，排序往往是为检索服务的。  
稳定性是排序方法本身的特性，一种排序方法如果稳定，则对所有数据序列都是稳定的；反过来，如果在一组数据上出现不稳定的现象，则该方法是不稳定的。（即：两个相等的数不会交换位置）

# 二、分类 #

## 1、外部排序 ##

待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程

## 2、内部排序 ##

待排序的记录全部存放在计算机内存中进行的排序过程，内部排序的方法：插入排序（直接插入排序、折半插入排序、表插入排序、希尔排序）、交换排序（冒泡排序、快速排序）、选择排序（直接选择排序、堆排序）、归并排序

在内部排序中，根据排序过程中依据的原则可以分为5类：

<table> 
 <thead> 
  <tr> 
   <th>插入排序</th> 
   <th>直接插入排序、折半插入排序、表插入排序、希尔排序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>交换排序</td> 
   <td>冒泡排序、快速排序</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>直接选择排序、堆排序</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>二路归并、多路归并</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

#  #

# 三、如何评价一个算法的优劣 #

通常使用时间复杂度和空间复杂度这两个指标，排序过程中主要比较两个键值大小和将记录从一个位置移动到另一个位置这两种基本操作。因此从键值的比较次数和记录的移动次数两个方面来分析时间复杂度  
由于排序算法的多样性，很难确定哪种算法是公认的最好的方法。

例如：当待排序序列已基本有序时，插入排序和交换排序比较有效；当待排记录数量较大时，选择排序比较有效。

评价标准：算法的运算量（主要通过记录的比较次数和移动次数来反应）、执行算法所需要的附加存储单元的多少

# 四、交换排序 #

## 1、冒泡排序 ##

### （1）未优化的冒泡： ###

public static void main(String[] args){ 
            int[] arr={ 15,12,4,1,19,30,25};
            //记录总共循环了多少次
            int count=0;
            //外层循环
            for(int i=1;i<arr.length;i++){ 
                //内层循环
                for(int j=0;j<arr.length-i;j++){ 
                    //两两比较：前一个数比后一个数大，就做交换
                    if(arr[j]>arr[j+1]){ 
                        int tmp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=tmp;
                    }
                    count++;
                    System.out.println(i+"-------"+j+"-------"+Arrays.toString(arr));
                }
            }
            System.out.println("循环次数："+count);
        }

![image.png][]

### （2）冒泡排序的优化：立flag，有序了就不排序了 ###

public static void main(String[] args){ 
            int[] arr={ 15,12,4,1,19,30,26};
            //记录总共循环了多少次
            int count=0;
            //外层循环
            for(int i=1;i<arr.length;i++){ 
                //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                boolean flag=true;
                //内层循环
                for(int j=0;j<arr.length-i;j++){ 
                    //前一个数比后一个数大，就做交换
                    if(arr[j]>arr[j+1]){ 
                        int tmp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=tmp;
    
                        flag=false;
                    }
                    System.out.println("外循环第"+i+"次"+"-------"+"内循环第"+j+"次"+"-------"+Arrays.toString(arr));
                    count++;
                    if(flag){ 
                        break;
                    }
                }
            }
            System.out.println("总的循环次数："+count);
        }

![image.png][image.png 1]

## 2、快速排序 ##

public class QuickSort { 
        public static int[] quickSort(int arr[],int start,int end) { 
            int pivot = arr[start];
            int i = start;
            int j = end;
            while (i<j) { 
                while ((i<j)&&(arr[j]>pivot)) { //从数组尾端开始与基准值做比较，如果比笔基准值大就j--（继续比较），否则交换
                    j--;
                }
                while ((i<j)&&(arr[i]<pivot)) { //从数组头部开始与基准值做比较，如果比笔基准值大就i++（继续比较），否则交换
                    i++;
                }
                if ((i<j)&&(arr[i]==arr[j])) { 
                    i++;
                } else { //交换
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                System.out.println(Arrays.toString(arr));
            }
    
            if (i-1>start) arr=quickSort(arr,start,i-1);
            if (j+1<end) arr=quickSort(arr,j+1,end);
            return arr;
        }
    
        public static void main(String[] args) { 
            int arr[] = new int[]{ 9, 8, 7, 6, 5, 4, 3, 2, 10};
            int len = arr.length-1;
            arr=quickSort(arr,0,len);
            System.out.println("最终结果："+Arrays.toString(arr));
        }
    }

## 3、二分查找（与快速排序做比较，勿混淆） ##

public class TwoPointsSearch { 
        public static void main(String[] args){ 
            int[] arr={ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
            twoPointsSearch(arr,1);
        }
    
        public static int twoPointsSearch(int[] arr, int val) { 
            //定义初始最小、最大索引
            int start = 0;
            int end = arr.length - 1;
            //确保不会出现重复查找，越界
            while (start <= end) { 
                //计算出中间索引值,>>>1 ——>防止溢出
                int middle = (end + start)>>>1 ;
                if (val == arr[middle]) { 
                    System.out.println("索引："+middle+",值："+arr[middle]);
                    return middle;
                } else if (val < arr[middle]) {  //判断下限
                    end = middle - 1;
                } else { //判断上限
                    start = middle + 1;
                }
            }
            //若没有，则返回-1
            return -1;
        }
    }

# 五、插入排序 #

## 1、直接插入 ##

基本思想：依次将每个记录插入到一个已经排好序的有序数据中去，从而得到一个新的、个数数加1的有序数据；类似图书馆中整理图书的过程。  
该算法适用于少量数据的排序  
时间复杂度：O(n^2)  
稳定排序

public static void main(String[] args){ 
            int[] arr={ 15,12,4,1,19,30,26};
            //从索引为1的元素开始选择合适的位置插入，因为索引为0的只有一个元素，默认是有序的
            for(int i=1;i<arr.length;i++){ 
                //记录要插入的数据
                int tmp=arr[i];
                int j=i;
                //当前数小于前一个数
                while (j>0&&tmp<arr[j-1]){ 
                    //把前一个数先往后挪
                    arr[j]=arr[j-1];
                    j--;
                }
                if(j!=i){ 
                    arr[j]=tmp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }

## 2、希尔排序 ##

public static void main(String[] args){ 
            int[] array={ 49,38,65,97,76,13,27,49,78};
            System.out.println("排序之前："+ Arrays.toString(array));
            
            int gap = array.length;
            while (true) { 
                gap /= 2;   //增量每次减半
                for (int i = 0; i < gap; i++) { 
                    for (int j = i + gap; j < array.length; j += gap) { //这个循环里其实就是一个插入排序
                        int temp = array[j];
                        int k = j - gap;
                        while (k >= 0 && array[k] > temp) { 
                            array[k + gap] = array[k];
                            k -= gap;
                        }
                        array[k + gap] = temp;
                    }
                    System.out.println(Arrays.toString(array));
                }
                if (gap == 1)
                    break;
            }
            
            System.out.println("排序之后："+Arrays.toString(array));
        }

# 六、选择排序 #

## 1、直接选择排序 ##

public static void main(String[] args){ 
            int[] arr={ 15,12,4,1,19,30,26};
            //记录循环次数
            int count=0;
            //总共要经过N-1次比较
            for(int i=0;i<arr.length-1;i++){ 
                //记录每轮比较中最小数的索引：每轮外层循环开始，假设当前索引的值是最小数
                int min=i;
                //每轮需要比较的次数：N-i
                for(int j=i+1;j<arr.length;j++){ 
                    if(arr[min]>arr[j]){ 
                        //记录目前能找到的最小值元素的索引
                        min=j;
                    }
                    count++;
                }
                //将找到的最小值和i位置所在的值进行交换
                if(i!=min){ 
                    int tmp=arr[i];
                    arr[i]=arr[min];
                    arr[min]=tmp;
                }
                System.out.println("外循环第"+i+"次"+Arrays.toString(arr));
            }
            System.out.println("总的循环次数："+count);
        }

![image.png][image.png 2]

## 2、堆排序 ##

# 七、归并排序 #

## 1、概述 ##

建立在归并操作上的一种有效的排序算法，该算法采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

## 2、工作原理 ##

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列  
2、设定两个指针，最初位置分别为两个已经排序排序列的起始位置  
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3，直到某一至指针超出序列尾  
将另一序列剩下的所有元素直接复制到合并序列尾

## 3、评价 ##

具有稳定性，比较次数小于快速排序的比价次数，移动次数一般多于快速排序的移动次数

速度仅次于快速排序，是稳定算法，一般用于对总体无序，但是各子项相对有序的数列

public class MergeSort { 
    
        public static int[] mergeSort(int[] nums, int low, int high) { 
            if (low == high)
                return new int[] {  nums[low] };
    
            int mid = low + (high - low) / 2;
            int[] leftArr = mergeSort(nums, low, mid); //左有序数组
            int[] rightArr = mergeSort(nums, mid + 1, high); //右有序数组
            int len=leftArr.length + rightArr.length;
            int[] newNum = new int[len]; //新有序数组
    
            int m = 0, i = 0, j = 0;
            while (i < leftArr.length && j < rightArr.length) { 
                newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
            }
            while (i < leftArr.length)
                newNum[m++] = leftArr[i++];
            while (j < rightArr.length)
                newNum[m++] = rightArr[j++];
            return newNum;
        }
        public static void main(String[] args) { 
            int[] nums = new int[] {  9, 8, 7, 6, 5, 4, 3, 2, 10 };
            int[] newNums = mergeSort(nums, 0, nums.length - 1);
            System.out.println(Arrays.toString(newNums));
        }
    
    }

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f41a1676afb048c1ab3b92e356383bc0.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/50e713982ddb4f399f02bbb2fda3b8a7.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/29b424a76247425a91512a1d46d47787.png