黑马程序员技术交流社区

标题: 整理下数组的排序方法 [打印本页]
作者: 氕氘氚    时间: 2015-8-5 20:39
标题: 整理下数组的排序方法
1.选择排序
选择排序是从a[0]开始，依次从原数组中取最小值，填入新数组中。
时间复杂度是O(n²)
  1. class SelectSort
  2. {
  3.         public void selectSort(int[] arr)
  4.         {
  5.                 for (int i = 0; i < arr.length - 1; i++)
  6.                 {
  7.                         for (int j = i + 1; j < arr.length; j++)
  8.                         {
  9.                                 if (arr[i] > arr[j])
  10.                                 {
  11.                                         int temp = arr[i];
  12.                                         arr[i] = arr[j];
  13.                                         arr[j] = temp;
  14.                                 }
  15.                         }
  16.                 }
  17.         }
  18. }
复制代码
作者: 氕氘氚    时间: 2015-8-5 20:46
2.冒牌排序
冒泡排序是数组中相邻的两数进行比较，一次循环后的效果是最大值填入a[n-1]
时间复杂度也是O(n²)
  1. class BubbleSort
  2. {
  3.         public void bubbleSort(int[] arr)
  4.         {
  5.                 for (int i = 0; i < arr.length; i++)
  6.                 {
  7.                         for (int j = 0; j < arr.length - i; j++)
  8.                         {
  9.                                 if (arr[j] > arr[j + 1])
  10.                                 {
  11.                                         swap(arr, j, j + 1);
  12.                                 }
  13.                         }
  14.                 }
  15.         }

  17.         public void swap(int[] arr, int a, int b)
  18.         {
  19.                 arr[a] ^= arr[b];
  20.                 arr[b] ^= arr[a];
  21.                 arr[a] ^= arr[b];
  22.         }
  23. }
复制代码
作者: 氕氘氚    时间: 2015-8-5 21:01
3.插入排序
插入排序是先将子数组排序，假如子数组长度为i，将第i+1个元素插入排好序的子数组中，循环插入，直到数组中的所有元素全部排序完成
  1. class InsertSort
  2. {
  3.         public void insertSort(int[] arr)
  4.         {
  5.                 for (int i = 1; i < arr.length; i++)
  6.                 {
  7.                         for (int j = 0; j < i; j++)
  8.                         {
  9.                                 if (arr[i] > arr[j])
  10.                                 {
  11.                                         swap(arr, i, j);
  12.                                 }
  13.                         }
  14.                 }
  15.         }

  17.         public void swap(int[] arr, int a, int b)
  18.         {
  19.                 arr[a] = arr[a] + arr[b];
  20.                 arr[b] = arr[a] - arr[b];
  21.                 arr[a] = arr[a] - arr[b];
  22.         }
  23. }
复制代码
作者: 小燕小男_爱情    时间: 2015-8-5 21:03
好人一生平安
作者: 氕氘氚    时间: 2015-8-5 22:16
4.快速排序
快速排序采用分治法，指定一个数，比它大的放在它的右边，比它小的放在它的左边。
然后这左边和右边的这两个子数组再进行相同的操作，递归调用，直到整个数组排序完成。
时间复杂度为O(n)
  1. class QuickSort
  2. {
  3.         public void quickSort(int[] arr, int i, int j)
  4.         {
  5.                         int end = getEnd(arr, i, j);
  6.                         quickSort(arr, i, end - 1);
  7.                         quickSort(arr, end + 1 , j);
  8.         }

  10.         public int getEnd(int[] arr, int i, int j)
  11.         {
  12.                 int temp = arr[i];
  13.                 while (i < j)
  14.                 {
  15.                         while (arr[j] > temp)
  16.                         {
  17.                                 j--;
  18.                         }
  19.                         arr[i] = arr[j];

  21.                         while (arr[i] < temp)
  22.                         {
  23.                                 i++;
  24.                         }
  25.                         arr[j] = arr[i];
  26.                 }
  27.                 arr[i] = temp;
  28.                 return i;
  29.         }
  30. }
复制代码
作者: java过客    时间: 2015-8-5 22:22
学习下，膜拜大水牛{:2_32:}
作者: hufan小步调    时间: 2015-8-5 22:29
后面两个没学
作者: 时光游戏    时间: 2015-8-5 22:35
学习了,膜拜大牛
作者: 风华正茂    时间: 2015-8-5 23:00
学习了，楼主辛苦了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2