首页 > 代码库 > 简单排序，冒泡排序，鸡尾酒排序，快速排序
简单排序，冒泡排序，鸡尾酒排序，快速排序
简单排序：每次找出最大（小）的数，从头开始依次排序。
1 public static int[] simplySort(int a[]) { 2 for (int i = 0; i < a.length - 1; i++) { 3 // int min = a[i]; 4 int minIndex = i; 5 for (int j =i + 1; j < a.length; j++) { 6 //我的代码 7 // if (a[j] < min) { 8 // min = a[j]; 9 // minIndex = j;10 // }11 //老师代码12 if (a[j] < a[minIndex]) {13 minIndex = j;14 }15 }16 // int m = a[i];17 // a[i] = a[minIndex];18 // a[minIndex] = m;19 if (i != minIndex) {
//"^"求异或20 a[i] = a[i] ^ a[minIndex];21 a[minIndex] = a[i] ^ a[minIndex];22 a[i] = a[i] ^ a[minIndex];23 }24 25 }26 return a;27 }
冒牌排序：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1 public int[] getSort(int[] array) { 2 boolean swapped = true; //循环控制 3 for (int i = 0; swapped && i < array.length - 1; i++) { 4 swapped = false; 5 for (int j = 0; j < array.length - i-1; j++) { 6 if (array[j] > array[j+1]) { 7 int temp = array[j]; 8 array[j] = array[j+1]; 9 array[j+1] = temp;10 swapped = true;//当没有做交换的时候，也就是说数列已经是有序的了，就不做循环了11 }12 }13 }14 return array;15 }
鸡尾酒排序：
与冒泡排序不同的地方：
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。
以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。
复杂度：
鸡尾酒排序最糟或是平均所花费的次数都是O(n^2)，但如果序列在一开始已经大部分排序过的话，会接近O（n）。
1 public static int[] cocktailSort(int[] a) { 2 for (int i = 0; i < a.length / 2; i++) { 3 for (int j = 0; j < a.length - i - 1; j++) { 4 if (a[j] > a[j + 1]) { 5 int tem = a[j]; 6 a[j] = a[j + 1]; 7 a[j + 1] = tem; 8 } 9 }10 for (int j = a.length - i - 1; j > 0; j--) {11 if (a[j] < a[j - 1]) {12 int tem = a[j];13 a[j] = a[j - 1];14 a[j - 1] = tem;15 }16 }17 }18 return a;19 }
快速排序：是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
具体步骤：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
1 public static int[] quickSort(int[] a, int start,int end) { 2 int low = start; 3 int high = end; 4 int pivot = a[low]; 5 while (low < high) { 6 while (low < high && a[high] >= pivot) { 7 high--; 8 } 9 if (low < high && a[high] < pivot) {10 int tem = a[low];11 a[low] = a[high];12 a[high] = tem;13 low++;14 }15 while (low < high && a[low] < pivot) {16 low++;17 }18 if (low < high && a[low] >= pivot) {19 int tem = a[low];20 a[low] = a[high];21 a[high] = tem;22 high--;23 }24 }25 if (low - 1 > start) {26 quickSort(a, start, low - 1);27 }28 if (high + 1 < end) {29 quickSort(a, low + 1, end);30 }31 32 return a;33 }
简单排序，冒泡排序，鸡尾酒排序，快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。