常见排序算法Java实现

男娘i 2024-04-17 16:07 58阅读 0赞

> 想起来去年的现在正在学习数据结构，时间好快哦。今天在微博加到一个漂亮女孩在的微信，她说看我评论比较搞笑，是我太沙雕了吗，不，不是的，我只是一个又皮又欠揍的可爱男孩子。

参考严蔚敏，吴伟民编著的《数据结构c语言版》，整理了几个常用的排序算法，用Java实现了。

package sorttest;
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class SortTest { 
        public static void main(String[] args) { 
            int nums[] = getNums();
    
    // buddleSort(nums);//冒泡排序
    
    // selectionSort(nums);//选择排序
    
    // insertionSort(nums);//插入排序
    
    // shellsort(nums);//希尔排序
    
    // nums = mergeSort(nums);//归并排序
    
            quickSort(nums);//快速排序
    
            for (int in : nums) { 
                System.out.print(in + " ");
            }
    
        }
    
        /** * 冒泡排序 * @param nums * @return */
       static void buddleSort(int[] nums) { 
            int length = nums.length;
            for (int i = length;i > 0; i--) { 
                for (int j = 0; j < i-1; j++) { 
                    if (nums[j] > nums[j+1]) { 
                        int tem = nums[j];
                        nums[j] = nums[j+1];
                        nums[j+1] = tem;
                    }
                }
            }
        }
    
        /** *选择排序 * @param nums * @return */
        static void selectionSort(int[] nums) { 
           int length = nums.length;
           for (int i = 0; i < length; i++) { 
               int min = i;
               for (int j = i; j < length; j++){ 
                   if (nums[j] < nums[min]) { 
                       min = j;
                   }
               }
               if (min != i) { 
                   int tem = nums[i];
                   nums[i] = nums[min];
                   nums[min] = tem;
               }
           }
        }
    
        /** *插入排序 * @param nums * @return */
        static void insertionSort(int[] nums) { 
            int length = nums.length;
            for (int i = 0; i < length-1; i++) { 
                int num = nums[i+1];
                int j = i;
               while (num < nums[j]) { 
                   nums[j+1] = nums[j];
                   j--;
               }
               nums[j+1] = num;
            }
        }
    
        /** *希尔排序 * @param nums * @return */
        static void shellsort(int[] nums) { 
            System.out.println();
            int length = nums.length;
            int gap = length/2;//增量
            while (gap > 0) { 
                for (int i = gap; i < length; i++) { 
                    int num = nums[i];
                    int j = i;
                    while (num < nums[j-gap]) { 
                        nums[j] = nums[j-gap];
                        j = j - gap;
                    }
                    nums[j] = num;
                }
                gap = gap/2;
            }
        }
    
        /** *归并排序 * @param nums */
        static int[] mergeSort(int[] nums) { 
            int mid = nums.length/2;
            if (nums.length > 1) { 
                int[] left = Arrays.copyOfRange(nums, 0, mid);
                int[] right = Arrays.copyOfRange(nums, mid, nums.length);
                return merge(mergeSort(left), mergeSort(right));
            } else return nums;
    
        }
    
        /** *归并算法 * @param left * @param right * @return */
        static int[] merge(int[] left,int[] right) { 
            int[] res = new int[left.length + right.length];
            int j = 0, i = 0, index = 0;
            for (index = 0; index < res.length; index++) { 
                if (i >= left.length) { 
                    res[index] = right[j++];
                }else if (j >= right.length) { 
                    res[index] = left[i++];
                } else if (left[i] < right[j]) { 
                    res[index] = left[i++];
                } else { 
                    res[index] = right[j++];
                }
            }
            return res;
        }
    
        /** * 快速排序 * @param nums */
        static void quickSort(int[] nums) { 
            int leftprivot = quikSortOne(nums, 0, nums.length-1);
            int rightprivot = leftprivot;
            while (leftprivot > 1) { 
                leftprivot = quikSortOne(nums, 0, leftprivot-1);
            }
            while (rightprivot < nums.length-2) { 
                rightprivot = quikSortOne(nums, rightprivot+1, nums.length-1);
            }
    
        }
    
        /** * 一趟快速排序 * @param nums * @param i 要排的数组起始位置 * @param j 要排的数组末尾位置 */
        static int quikSortOne(int[] nums, int i, int j) { 
            int low = i;
            int high = j;
            int privotkey = nums[i];
            int privot = i;
            while (low < high) { 
                while (low < high && privotkey <= nums[high]) high--;
                int tem1 = nums[high];
                nums[high] = nums[low];
                nums[low] = tem1;
                privot = high;
                while (low < high && privotkey >= nums[low]) low++;
                int tem2 = nums[high];
                nums[high] = nums[low];
                nums[low] = tem2;
                privot = low;
            }
            return privot;
        }
    
    
    
        /** * 输入函数 * @return */
        static int[] getNums() { 
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            String[] ss = s.split(" ");
            int[] nums = new int[ss.length];
            int k = 0;
            for (String s1 : ss) { 
                nums[k] = Integer.valueOf(s1);
                k++;
            }
    
            return nums;
        }
    }