Java之排序总结-白红宇

Java之排序总结

阅读量：4947 次

发布时间：2019-06-11

本文共 9301 字，大约阅读时间需要 31 分钟。

public class SortTest {
   public int[] createArray() {
                 Random random = new Random(); int[] array = new int[10]; for (int i = 0; i < 10; i++) {
                        array[i] = random.nextInt(100) - random.nextInt(100);//生成两个随机数相减，保证生成的数中有负数               }               System.out.println("==========原始序列==========");               printArray(array); return array;        } public void printArray(int[] data) {
   for (int i : data) {
                        System.out.print(i + " ");               }               System.out.println();        } private void swap(int[] data, int x, int y) {
   int temp = data[x];               data[x] = data[y];               data[y] = temp;        }

　　　　//冒泡排序，时间复杂度：O(n)~O(n2),空间复杂度：O(1),稳定性：稳定排序，适用性：数组基本有序时排序较快 public void bubbleSort(int[] data, String sortType) {
   if (sortType.equals("asc")) { //正排序，从小排到大 //比较的轮数                      for (int i = 1; i < data.length; i++) {
   //将相邻两个数进行比较，较大的数往后冒泡                             for (int j = 0; j < data.length - i; j++) {
   if (data[j] > data[j + 1]) {
   //交换相邻两个数                                           swap(data, j, j + 1);                                    }                             }                      }               } else if (sortType.equals("desc")) { //倒排序，从大排到小 //比较的轮数                      for (int i = 1; i < data.length; i++) {
   //将相邻两个数进行比较，较大的数往后冒泡                             for (int j = 0; j < data.length - i; j++) {
   if (data[j] < data[j + 1]) {
   //交换相邻两个数                                           swap(data, j, j + 1);                                    }                             }                      }               } else {
                        System.out.println("您输入的排序类型错误！");               }               printArray(data);//输出冒泡排序后的数组值        }

　　　　 //选择排序，时间复杂度：O(n2),空间复杂度：O(1),不稳定。

算法思想：每次从无序数组中选出一个最小的出来，放到已经排好的数组的前面(或后面)

public void selectSort(int[] data, String sortType) {
   if (sortType.equals("asc")) { //正排序，从小排到大                      int index; for (int i = 1; i < data.length; i++) {
                               index = 0; for (int j = 1; j <= data.length - i; j++) {
   if (data[j] > data[index]) {
                                             index = j;                                    }                             } //交换在位置data.length-i和index(最大值)两个数                             swap(data, data.length - i, index);                      }               } else if (sortType.equals("desc")) { //倒排序，从大排到小                      int index; for (int i = 1; i < data.length; i++) {
                               index = 0; for (int j = 1; j <= data.length - i; j++) {
   if (data[j] < data[index]) {
                                             index = j;                                    }                             } //交换在位置data.length-i和index(最大值)两个数                             swap(data, data.length - i, index);                      }               } else {
                        System.out.println("您输入的排序类型错误！");               }               printArray(data);//输出直接选择排序后的数组值        } //插入排序，空间复杂度：O(n2),空间复杂度：O(1),稳定。算法思想：逐一取出元素，在已排好的元素序列中从后向前扫描，插入到适当的位置 public void insertSort(int[] data, String sortType) {
   if (sortType.equals("asc")) { //正排序，从小排到大 //比较的轮数                      for (int i = 1; i < data.length; i++) {
   //保证前i+1个数排好序                             for (int j = 0; j < i; j++) {
   if (data[j] > data[i]) {
   //交换在位置j和i两个数                                           swap(data, i, j);                                    }                             }                      }               } else if (sortType.equals("desc")) { //倒排序，从大排到小 //比较的轮数                      for (int i = 1; i < data.length; i++) {
   //保证前i+1个数排好序                             for (int j = 0; j < i; j++) {
   if (data[j] < data[i]) {
   //交换在位置j和i两个数                                           swap(data, i, j);                                    }                             }                      }               } else {
                        System.out.println("您输入的排序类型错误！");               }               printArray(data);//输出插入排序后的数组值        } public void reverse(int[] data) {
   int length = data.length; int temp = 0;//临时变量  for (int i = 0; i < length / 2; i++) {
                        temp = data[i];                      data[i] = data[length - 1 - i];                      data[length - 1 - i] = temp;               }               printArray(data);//输出到转后数组的值        } /*快速排序，时间复杂度：O(nlogn)，空间复杂度：O(logn)，不稳定。基本思想：第一趟把待排序数据分成独立的两部分，其中一部分所有数据都比另外一部分小，然后再对这两部分分别进行快速排序，整个过程递归，已达到整个数据变成有序数据*/ public void quickSort(int[] data, String sortType) {
   if (sortType.equals("asc")) { //正排序，从小排到大                      qsort_asc(data, 0, data.length - 1);               } else if (sortType.equals("desc")) { //倒排序，从大排到小                      qsort_desc(data, 0, data.length - 1);               } else {
                        System.out.println("您输入的排序类型错误！");               }        } private void qsort_asc(int data[], int low, int high) {
   int i, j, x; if (low < high) { //这个条件用来结束递归                      i = low;                      j = high;                      x = data[i]; while (i < j) {
   while (i < j && data[j] > x) { j--; }  //从右向左找第一个小于x的数 if (i < j) { data[i] = data[j]; i++;} while (i < j && data[i] < x) { i++; }  //从左向右找第一个大于x的数 if (i < j) { data[j] = data[i]; j--;}                      }                      data[i] = x;                      qsort_asc(data, low, i - 1);                      qsort_asc(data, i + 1, high);               }        } private void qsort_desc(int data[], int low, int high) {
   int i, j, x; if (low < high) { //这个条件用来结束递归                      i = low;                      j = high;                      x = data[i]; while (i < j) {
   while (i < j && data[j] < x) { j--; }  //从右向左找第一个小于x的数 if (i < j) { data[i] = data[j]; i++;} while (i < j && data[i] > x) { i++; }  //从左向右找第一个大于x的数 if (i < j) { data[j] = data[i]; j--;}                      }                      data[i] = x;                      qsort_desc(data, low, i - 1);                      qsort_desc(data, i + 1, high);               }        } //二分法查找算法一，时间复杂度O(logn) public int binarySearch(int[] dataset, int data, int beginIndex, int endIndex) {
   int midIndex = (beginIndex + endIndex) / 2;               if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) return -1; if (data < dataset[midIndex]) {
   return binarySearch(dataset, data, beginIndex, midIndex - 1);               } else if (data > dataset[midIndex]) {
   return binarySearch(dataset, data, midIndex + 1, endIndex);               } else {
   return midIndex;               }        }  //二分法查找算法二，时间复杂度O(logn) public int binarySearch(int[] dataset, int data) {
   int beginIndex = 0; int endIndex = dataset.length - 1; int midIndex = -1; if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) return -1; while (beginIndex <= endIndex) {
                        midIndex = (beginIndex + endIndex) / 2; //相当于midIndex = (beginIndex + endIndex) / 2，但是效率会高些                      if (data < dataset[midIndex]) {
                               endIndex = midIndex - 1;                      } else if (data > dataset[midIndex]) {
                               beginIndex = midIndex + 1;                      } else {
   return midIndex;                      }               } return -1;        } public static void main(String[] args) {
                 SortTest sortTest = new SortTest(); int[] array = sortTest.createArray();               System.out.println("==========冒泡排序后(正序)==========");               sortTest.bubbleSort(array, "asc");               System.out.println("==========冒泡排序后(倒序)==========");               sortTest.bubbleSort(array, "desc");               array = sortTest.createArray();               System.out.println("==========倒转数组后==========");               sortTest.reverse(array);               array = sortTest.createArray();               System.out.println("==========选择排序后(正序)==========");               sortTest.selectSort(array, "asc");               System.out.println("==========选择排序后(倒序)==========");               sortTest.selectSort(array, "desc");               array = sortTest.createArray();               System.out.println("==========插入排序后(正序)==========");               sortTest.insertSort(array, "asc");               System.out.println("==========插入排序后(倒序)==========");               sortTest.insertSort(array, "desc");               array = sortTest.createArray();               System.out.println("==========快速排序后(正序)==========");               sortTest.quickSort(array, "asc");               sortTest.printArray(array);               System.out.println("==========快速排序后(倒序)==========");               sortTest.quickSort(array, "desc");               sortTest.printArray(array);               System.out.println("==========数组二分查找==========");               System.out.println("您要找的数在第" + sortTest.binarySearch(array, 74) + "个位子。（下标从0计算）");        } }