数据结构复习—排序实现总结(Java实现)

你的名字 2023-02-21 02:24 16阅读 0赞

### 冒泡排序 ###

n-1趟排序，每趟都能确定一个位置。

public class BubbleSort {
        
        private static void bubbleSort(int[] arr) {
        
            boolean isSwap;
            int n = arr.length;
            // n-1趟
            for (int i = 0; i < n - 1; i++) {
        
                // 从后到前，两两交换，每趟都能确定一个位置
                // 判断这一趟是否有交换，如无，则已经有序
                isSwap = false;
                for (int j =  n - 1; j > 0; j--) {
        
                    if (arr[j - 1] > arr[j]) {
        
                        //交换操作
                        int tmp = arr[j - 1];
                        arr[j - 1] = arr[j];
                        arr[j] = tmp;
                        isSwap = true;
                    }
                }
                if (!isSwap) {
        
                    break;
                }
            }
            //打印
            System.out.println(Arrays.toString(arr));
        }
        public static void main(String[] args) {
        
            int[] arr = {
        9, 8, 7, 6, 5, 4, 3, 2, 1};
            int[] arr1 = {
        55,425,33,22,65,789};
            bubbleSort(arr);
            bubbleSort(arr1);
        }
    }
    // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    // [22, 33, 55, 65, 425, 789]
    // Process finished with exit code 0

### 快速排序 ###

快速排序主要是划分和递归两个操作。在一次划分之后，可以将序列分为两个小序列，再分别递归进行同样的操作。

划分，思想为：以一个元素作为轴，表中比轴大的元素往右走，表中比轴小的元素向左移动。

具体实现为：以严书为例，初始选择第一个元素为”枢纽“,然后不断地："**从high向左寻找比枢纽小的元素，并与low进行交换，再从low向右寻找比枢纽大的，与high进行交换**” ，直到`low`等于`high`。

以上便是一次划分。

public static int partition(int[] arr,int low,int high)
        {
        
            int flag = arr[low];
            while(low<high)
            {
        
                while(low<high && arr[high]>=flag) {
        
                    --high;
                }
                arr[low] = arr[high];
                while(low<high && arr[low]<=flag) {
        
                    ++low;
                }
                arr[high] = arr[low];
            }
            arr[low] = flag;
            return low;
        }

递归操作

public static void quickSort(int[] arr,int low,int high)
        {
        
           if(low<high)
           {
        
           	   // 这里的flag也就是快速排序划分过程中的"枢纽"	
               int flag = partition(arr,low,high);
               quickSort(arr,low,flag-1);
               quickSort(arr,flag+1,high);
           }
    
        }
    public static void main(String[] args) {
        
         int[] arr = {
        9, 8, 7, 6, 5, 4, 3, 2, 1};
    
         quickSort(arr,0,arr.length-1);
         //打印
         System.out.println(Arrays.toString(arr));
     }
     // [1, 2, 3, 4, 5, 6, 7, 8, 9]

### 简单选择排序 ###

思想：每次从待排序列中，选择关键字最小（最大）的，放到有序序列中。

public static void selectSort(int[] arr)
        {
        
            for(int i=0;i<arr.length-1;i++)
            {
        
                int min = i;
                // 找到最小值
                for(int j=i+1;j<arr.length;j++)
                {
        
                    if(arr[min]>arr[j])
                    {
        
                        min = j;
                    }
                }
                // 交换
                if(min != i)
                {
        
                    int temp = arr[min];
                    arr[min] = arr[i];
                    arr[i] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }