几种排序算法及Java实现排序的几种方式

几种排序算法

下面的例子介绍了4种排序方法: 冒泡排序, 选择排序, 插入排序, 快速排序

 package date201709.date20170915;

 public class SortUtil {

     private static int quickSortTimes = 1;

     /**

      * 冒泡排序:<br>

      * 两层循环，每次循环比较前后两个元素，如果他们的顺序错误就把他们交换过来，一次循环后最终会把最大的数沉到数列的末端<br>

      * 下次循环时,上次循环沉到数列的末端的数不用再参与到本次循环中来比较<br>

      */

     // 第1次排序结果: 30 59 12 46 15 83 10 59 27 91

     // 第2次排序结果: 30 12 46 15 59 10 59 27 83 91

     // 第3次排序结果: 12 30 15 46 10 59 27 59 83 91

     // 第4次排序结果: 12 15 30 10 46 27 59 59 83 91

     // 第5次排序结果: 12 15 10 30 27 46 59 59 83 91

     // 第6次排序结果: 12 10 15 27 30 46 59 59 83 91

     // 第7次排序结果: 10 12 15 27 30 46 59 59 83 91

     // 第8次排序结果: 10 12 15 27 30 46 59 59 83 91

     // 第9次排序结果: 10 12 15 27 30 46 59 59 83 91

     public static void bubbleSort(int[] nums) {

         int temp = 0;

         int size = nums.length;

         for (int i = 0; i < size - 1; i++) {

             for (int j = 0; j < size - 1 - i; j++) {

                 if (nums[j] > nums[j + 1]) {

                     temp = nums[j];

                     nums[j] = nums[j + 1];

                     nums[j + 1] = temp;

                 }

             }

             printLog(nums, i + 1);

         }

     }

     /**

      * 选择排序:<br>

      * 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环<br>

      */

     // 第1次排序结果: 10 83 59 12 46 15 91 30 59 27

     // 第2次排序结果: 10 12 59 83 46 15 91 30 59 27

     // 第3次排序结果: 10 12 15 83 46 59 91 30 59 27

     // 第4次排序结果: 10 12 15 27 46 59 91 30 59 83

     // 第5次排序结果: 10 12 15 27 30 59 91 46 59 83

     // 第6次排序结果: 10 12 15 27 30 46 91 59 59 83

     // 第7次排序结果: 10 12 15 27 30 46 59 91 59 83

     // 第8次排序结果: 10 12 15 27 30 46 59 59 91 83

     // 第9次排序结果: 10 12 15 27 30 46 59 59 83 91

     public static void selectSort(int[] nums) {

         int temp = 0;

         int size = nums.length;

         for (int i = 0; i < size - 1; i++) {

             // 记录每一次循环最小值的位置

             int pos = i;

             for (int j = i + 1; j < size; j++) {

                 if (nums[pos] > nums[j]) {

                     pos = j;

                 }

             }

             // 最小的数与第i个位置的数交换

             temp = nums[i];

             nums[i] = nums[pos];

             nums[pos] = temp;

             printLog(nums, i + 1);

         }

     }

     /**

      * 插入排序<br>

      * 每步将一个待排序的记录，按其大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。<br>

      */

     // 第1次排序结果: 30 83 59 12 46 15 91 10 59 27

     // 第2次排序结果: 30 59 83 12 46 15 91 10 59 27

     // 第3次排序结果: 12 30 59 83 46 15 91 10 59 27

     // 第4次排序结果: 12 30 46 59 83 15 91 10 59 27

     // 第5次排序结果: 12 15 30 46 59 83 91 10 59 27

     // 第6次排序结果: 12 15 30 46 59 83 91 10 59 27

     // 第7次排序结果: 10 12 15 30 46 59 83 91 59 27

     // 第8次排序结果: 10 12 15 30 46 59 59 83 91 27

     // 第9次排序结果: 10 12 15 27 30 46 59 59 83 91

     private static void insertSort(int[] nums) {

         int temp = 0;

         int size = nums.length;

         // 从第2个元素开始，第1个元素可以认为已经被排序

         for (int i = 1; i < size; i++) {

             // 取出下一个元素

             temp = nums[i];

             // 在已经排序的元素序列中从前向后扫描

             for (int j = 0; j < i; j++) {

                 // 假如temp比前面的某个值小，则将这个值及之后的值后移

                 if (temp < nums[j]) {

                     for (int k = i; k > j; k--) {

                         nums[k] = nums[k - 1];

                     }

                     nums[j] = temp;

                     break;

                 }

             }

             printLog(nums, i);

         }

     }

     /**

      * 快速排序:<br>

      * 选取当前数组段的第一个数作为中轴，和最后一个比，如果比它小交换，比它大(或相等)不做任何处理<br>

      * 交换了以后再和小的那端比，比它小不交换，比他大交换<br>

      * 这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再递归对左边和右边的数组排序<br>

      */

     // 第1次排序结果: 27 10 15 12 30 46 91 59 59 83

     // 第2次排序结果: 12 10 15 27 -- -- -- -- -- --

     // 第3次排序结果: 10 12 15 -- -- -- -- -- -- --

     // 第4次排序结果: -- -- -- -- -- 46 91 59 59 83

     // 第5次排序结果: -- -- -- -- -- -- 83 59 59 91

     // 第6次排序结果: -- -- -- -- -- -- 59 59 83 --

     // 第7次排序结果: -- -- -- -- -- -- 59 59 -- --

     public static void quickSort(int[] numbers) {

         if (numbers.length > 1) {

             quickSort(numbers, 0, numbers.length - 1);

         }

     }

     private static void quickSort(int[] nums, int low, int high) {

         if (low < high) {

             // 选取中轴

             int middle = getMiddle(nums, low, high);

             printQuickSortLog(nums, low, high);

             if (low < middle - 1) {

                 // 对低字段表进行递归排序

                 quickSort(nums, low, middle - 1);

             }

             if (middle + 1 < high) {

                 // 对高字段表进行递归排序

                 quickSort(nums, middle + 1, high);

             }

         }

     }

     private static int getMiddle(int[] nums, int low, int high) {

         // 选取当前数组段的第一个数作为中轴

         int temp = nums[low];

         while (low < high) {

             // 比中轴大(或相等)不做任何处理(high--)，直到找到比中轴小的

             while (low < high && nums[high] >= temp) {

                 high--;

             }

             // 比中轴小的记录移到低端

             nums[low] = nums[high];

             // 比中轴小不做任何处理(low++)，直到找到比中轴大(或相等)的

             while (low < high && nums[low] < temp) {

                 low++;

             }

             // 比中轴大(或相等)的记录移到高端

             nums[high] = nums[low];

         }

         // 中轴记录到尾

         nums[low] = temp;

         // 返回中轴的位置

         return low;

     }

     private static void printLog(int[] nums, int times) {

         System.out.println("第" + times + "次排序结果:\t" + formatNums(nums));

     }

     private static void printQuickSortLog(int[] nums, int low, int high) {

         System.out.println("第" + quickSortTimes++ + "次排序结果:\t" + formatNums(nums, low, high));

     }

     private static String formatNums(int[] nums) {

         return formatNums(nums, 0, nums.length - 1);

     }

     private static String formatNums(int[] nums, int low, int high) {

         StringBuilder sb = new StringBuilder();

         for (int i = 0; i < low; i++) {

             sb.append("-- ");

         }

         for (int i = low; i <= high; i++) {

             sb.append(nums[i]).append(" ");

         }

         for (int i = high + 1; i < nums.length; i++) {

             sb.append("-- ");

         }

         return sb.toString().trim();

     }

     public static void main(String[] args) {

         // 10, 12, 15, 27, 30, 46, 59, 59, 83, 91

         int[] nums = { 30, 83, 59, 12, 46, 15, 91, 10, 59, 27 };

         // bubbleSort(nums);

         // selectSort(nums);

         // insertSort(nums);

         // quickSort(nums);

     }

 }

Java实现排序的几种方式

(1) 需要排序的Bean实现Comparable<T>接口

 package date201709.date20170915;

 import java.io.Serializable;

 import java.util.ArrayList;

 import java.util.List;

 public class User implements Serializable, Comparable<User> {

     private static final long serialVersionUID = 1L;

     private Integer id;

     private Integer age;

     private String name;

     public User(Integer id, Integer age, String name) {

         super();

         this.id = id;

         this.age = age;

         this.name = name;

     }

     public Integer getId() {

         return id;

     }

     public Integer getAge() {

         return age;

     }

     public String getName() {

         return name;

     }

     @Override

     public String toString() {

         return "User [id=" + id + ", age=" + age + ", name=" + name + "]";

     }

     @SuppressWarnings("serial")

     public static List<User> init() {

         return new ArrayList<User>() {

             {

                 add(new User(5, 31, "Zhang San"));

                 add(new User(2, 28, "Li Si"));

                 add(new User(3, 26, "Wang Wu"));

                 add(new User(1, 23, "Zhao Liu"));

                 add(new User(4, 26, "Liu Qi"));

             }

         };

     }

     // 比较ID从而对User排序

     @Override

     public int compareTo(User o) {

         return this.getId().compareTo(o.getId());

     }

 }

 package date201709.date20170915;

 import java.util.Collections;

 import java.util.List;

 public class UserTest {

     public static void main(String[] args) {

         // (1) Id升序

         List<User> userList = User.init();

         Collections.sort(userList);

         printList(userList);

         // (2) Id降序

         Collections.reverse(userList);

         printList(userList);

     }

     private static void printList(List<User> param) {

         param.forEach(p -> {

             System.out.println(p.toString());

         });

     }

 }

(2) 使用内部类实现Comparator<T>接口

 package date201709.date20170915;

 import java.util.Collections;

 import java.util.Comparator;

 import java.util.List;

 public class UserTest {

     public static void main(String[] args) {

         // (1) Age升序

         List<User> userList = User.init();

         Collections.sort(userList, new AgeComparator());

         printList(userList);

         // (2) Age降序

         Collections.reverse(userList);

         printList(userList);

     }

     private static void printList(List<User> param) {

         param.forEach(p -> {

             System.out.println(p.toString());

         });

     }

     static class AgeComparator implements Comparator<User> {

         @Override

         public int compare(User o1, User o2) {

             return o1.getAge().compareTo(o2.getAge());

         }

     }

 }

(3) 使用匿名内部类实现Comparator<T>接口

 package date201709.date20170915;

 import java.util.Collections;

 import java.util.Comparator;

 import java.util.List;

 public class UserTest {

     public static void main(String[] args) {

         // (1) Age升序

         List<User> userList = User.init();

         Collections.sort(userList, new Comparator<User>() {

             @Override

             public int compare(User o1, User o2) {

                 return o1.getAge().compareTo(o2.getAge());

             }

         });

         printList(userList);

         // (2) Age降序

         Collections.reverse(userList);

         printList(userList);

     }

     private static void printList(List<User> param) {

         param.forEach(p -> {

             System.out.println(p.toString());

         });

     }

 }

(4) 使用lambda表达式

 package date201709.date20170915;

 import java.util.Collections;

 import java.util.List;

 public class UserTest {

     public static void main(String[] args) {

         // (1) Age升序

         List<User> userList = User.init();

         Collections.sort(userList, (a, b) -> (a.getAge().compareTo(b.getAge())));

         printList(userList);

         // (2) Age降序

         Collections.reverse(userList);

         printList(userList);

     }

     private static void printList(List<User> param) {

         param.forEach(p -> {

             System.out.println(p.toString());

         });

     }

 }

(5) 使用stream及::表达式

 package date201709.date20170915;

 import java.util.Comparator;

 import java.util.List;

 import java.util.stream.Collectors;

 public class UserTest {

     public static void main(String[] args) {

         // (1) Age升序

         List<User> userList = User.init();

         List<User> result1 = userList.stream().sorted((a, b) -> a.getAge().compareTo(b.getAge()))

                 .collect(Collectors.toList());

         printList(result1);

         // (2) Age降序

         List<User> result2 = userList.stream().sorted(Comparator.comparing(User::getAge).reversed())

                 .collect(Collectors.toList());

         printList(result2);

     }

     private static void printList(List<User> param) {

         param.forEach(p -> {

             System.out.println(p.toString());

         });

     }

 }

巴特西

几种排序算法及Java实现排序的几种方式

最新文章

热门文章