黑马程序员技术交流社区

标题: 关于排序的问题 [打印本页]
作者: linder_qzy    时间: 2015-3-7 13:12
标题: 关于排序的问题
除了冒泡排序和选择排序以外，还有什么排序算法吗
最好把思想给讲讲 贴上点代码看看
作者: ZZGFF    时间: 2015-3-7 13:23
要说排序算法太多了。 好像有本书专门写这个的。 挺多种
作者: 千殇一梦    时间: 2015-3-7 14:06
听他们说看算法导论。{:3_57:}
作者: 路文龙    时间: 2015-3-7 14:27
  日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  1. package test.sort;   
  2. /**
  3. * 冒泡法排序<br/>  
  4. * <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>  
  5. * <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>  
  6. * <li>针对所有的元素重复以上的步骤，除了最后一个。</li>  
  7. * <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>  
  8. *   
  9. * @param numbers  
  10. *            需要排序的整型数组  
  11. */  
  12. public static void bubbleSort(int[] numbers) {   
  13.     int temp; // 记录临时中间值   
  14.     int size = numbers.length; // 数组大小   
  15.     for (int i = 0; i < size - 1; i++) {   
  16.         for (int j = i + 1; j < size; j++) {   
  17.             if (numbers[i] < numbers[j]) { // 交换两数的位置   
  18.                 temp = numbers[i];   
  19.                 numbers[i] = numbers[j];   
  20.                 numbers[j] = temp;   
  21.             }   
  22.         }   
  23.     }   
  24. }
复制代码
快速排序使用分治法策略来把一个序列分为两个子序列。
  1. package test.sort;   
  2. /**
  3. * 快速排序<br/>  
  4. * <ul>  
  5. * <li>从数列中挑出一个元素，称为“基准”</li>  
  6. * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，  
  7. * 该基准是它的最后位置。这个称为分割（partition）操作。</li>  
  8. * <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>  
  9. * </ul>  
  10. *   
  11. * @param numbers  
  12. * @param start  
  13. * @param end  
  14. */  
  15. public static void quickSort(int[] numbers, int start, int end) {   
  16.     if (start < end) {   
  17.         int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）   
  18.         int temp; // 记录临时中间值   
  19.         int i = start, j = end;   
  20.         do {   
  21.             while ((numbers[i] < base) && (i < end))   
  22.                 i++;   
  23.             while ((numbers[j] > base) && (j > start))   
  24.                 j--;   
  25.             if (i <= j) {   
  26.                 temp = numbers[i];   
  27.                 numbers[i] = numbers[j];   
  28.                 numbers[j] = temp;   
  29.                 i++;   
  30.                 j--;   
  31.             }   
  32.         } while (i <= j);   
  33.         if (start < j)   
  34.             quickSort(numbers, start, j);   
  35.         if (end > i)   
  36.             quickSort(numbers, i, end);   
  37.     }   
  38. }
复制代码

选择排序是一种简单直观的排序方法，每次寻找序列中的最小值，然后放在最末尾的位置。
  1. package test.sort;   
  2. /**
  3. * 选择排序<br/>  
  4. * <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li>  
  5. * <li>再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。</li>  
  6. * <li>以此类推，直到所有元素均排序完毕。</li>  

  8. *   
  9. * @param numbers  
  10. */  
  11. public static void selectSort(int[] numbers) {   
  12.     int size = numbers.length, temp;   
  13.     for (int i = 0; i < size; i++) {   
  14.         int k = i;   
  15.         for (int j = size - 1; j >i; j--)  {   
  16.             if (numbers[j] < numbers[k])  k = j;   
  17.         }   
  18.         temp = numbers[i];   
  19.         numbers[i] = numbers[k];   
  20.         numbers[k] = temp;   
  21.     }   
  22. }
复制代码

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其具体步骤参见代码及注释。
  1. package test.sort;   
  2. /**
  3. * 插入排序<br/>  
  4. * <ul>  
  5. * <li>从第一个元素开始，该元素可以认为已经被排序</li>  
  6. * <li>取出下一个元素，在已经排序的元素序列中从后向前扫描</li>  
  7. * <li>如果该元素（已排序）大于新元素，将该元素移到下一位置</li>  
  8. * <li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</li>  
  9. * <li>将新元素插入到该位置中</li>  
  10. * <li>重复步骤2</li>  
  11. * </ul>  
  12. *   
  13. * @param numbers  
  14. */  
  15. public static void insertSort(int[] numbers) {   
  16.     int size = numbers.length, temp, j;   
  17.     for(int i=1; i<size; i++) {   
  18.         temp = numbers[i];   
  19.         for(j = i; j > 0 && temp < numbers[j-1]; j--)   
  20.             numbers[j] = numbers[j-1];   
  21.         numbers[j] = temp;   
  22.     }   
  23. }
复制代码

归并排序是建立在归并操作上的一种有效的排序算法，归并是指将两个已经排序的序列合并成一个序列的操作。参考代码如下：
  1. package test.sort;   
  2. /**
  3. * 归并排序<br/>  
  4. * <ul>  
  5. * <li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列</li>  
  6. * <li>设定两个指针，最初位置分别为两个已经排序序列的起始位置</li>  
  7. * <li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置</li>  
  8. * <li>重复步骤3直到某一指针达到序列尾</li>  
  9. * <li>将另一序列剩下的所有元素直接复制到合并序列尾</li>  
  10. * </ul>  
  11. *   
  12. * @param numbers  
  13. */  
  14. public static void mergeSort(int[] numbers, int left, int right) {   
  15.     int t = 1;// 每组元素个数   
  16.     int size = right - left + 1;   
  17.     while (t < size) {   
  18.         int s = t;// 本次循环每组元素个数   
  19.         t = 2 * s;   
  20.         int i = left;   
  21.         while (i + (t - 1) < size) {   
  22.             merge(numbers, i, i + (s - 1), i + (t - 1));   
  23.             i += t;   
  24.         }   
  25.         if (i + (s - 1) < right)   
  26.             merge(numbers, i, i + (s - 1), right);   
  27.     }   
  28. }   
  29. /**  
  30. * 归并算法实现  
  31. *   
  32. * @param data  
  33. * @param p  
  34. * @param q  
  35. * @param r  
  36. */  
  37. private static void merge(int[] data, int p, int q, int r) {   
  38.     int[] B = new int[data.length];   
  39.     int s = p;   
  40.     int t = q + 1;   
  41.     int k = p;   
  42.     while (s <= q && t <= r) {   
  43.         if (data[s] <= data[t]) {   
  44.             B[k] = data[s];   
  45.             s++;   
  46.         } else {   
  47.             B[k] = data[t];   
  48.             t++;   
  49.         }   
  50.         k++;   
  51.     }   
  52.     if (s == q + 1)   
  53.         B[k++] = data[t++];   
  54.     else  
  55.         B[k++] = data[s++];   
  56.     for (int i = p; i <= r; i++)   
  57.         data[i] = B[i];   
  58. }
复制代码



作者: konglingzhiyu    时间: 2015-3-7 23:57
有很多个。冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序。
冒泡比较实用！
作者: 长工射日    时间: 2015-3-8 00:01
在Java里面有排序程序为java.util.array.sort
作者: zgjswp    时间: 2015-3-8 02:03
排序方法有很多啊，数据结构有讲的，分内部排序和外部排序两大类
作者: gaopeng868988    时间: 2015-3-8 08:56
排序 主流七大排序，
package ds;

/*
* author : codinglion
* contact: chenyakun@foxmail.com
*/

import java.util.Random;

publicclass Sorts {

// 冒泡排序
// 小数往上冒
public static int[] BubbleSort(int[] disOrderArray) {

int temp;
// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）
for (int i = 0; i < disOrderArray.length - 1; i++) {

// 把最小的数交换着"冒泡"的相对的最上边,一次冒上来的是最小的,其次是第二小的.
// length-1: 取数据最后一个数下标
// j>i 从后往前的下标一定大于从前往后的下标,否则越界了
for (int j = disOrderArray.length - 1; j > i; j--) {

if (disOrderArray[j] < disOrderArray[j - 1]) {
temp = disOrderArray[j];
disOrderArray[j] = disOrderArray[j - 1];
disOrderArray[j - 1] = temp;
}
}

}

// for (int element : disOrderArray) {
//
// System.out.print(element + " ");
// }
return disOrderArray;

}

/*
*
* 快速排序
*
* 思想:
* 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,
* 则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的
*
* 本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base
* 首先从序列最右边开始找比base小的
* ,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大
* 然后,从序列的最左边开始找比base大的
* ,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小
*
* 循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归
*/

public static int[] quickSort(int[] arr, int low, int heigh) {

if (low < heigh) {

int division = partition(arr, low, heigh);

quickSort(arr, low, division - 1);

quickSort(arr, division + 1, heigh);
}
return arr;

}

// 分水岭,基位,左边的都比这个位置小,右边的都大
public static int partition(int[] arr, int low, int heigh) {

int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录

while (low < heigh) {  //从表的两端交替向中间扫描

while (low < heigh && arr[heigh] >= base) {
heigh--;
}

// base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大
swap(arr, heigh, low);

while (low < heigh && arr[low] <= base) {
low++;
}
// 遇到左边比base值大的了,换位置
swap(arr, heigh, low);

}

// now low = heigh;
return low;
}

private static void swap(int[] arr, int a, int b) {
int temp;
temp = arr[a];
arr[a] = arr;
arr = temp;
}

/*
*
* 直接选择排序
*/
public static int[] selectionSort(int[] arr) {

for (int i = 0; i < arr.length; i++) {

int miniPos = miniPos(arr, i, arr.length);

if (arr > arr[miniPos]) {
swap(arr, i, miniPos);
}

}

returnnull;
}

// 返回最小的时序列中的哪一位
public static int miniPos(int[] arr, int from, int end) {

int miniPost = from;
for (int i = from + 1; i < end; i++) {

if (arr < arr[miniPost]) {
miniPost = i;
}
}
return miniPost;
}

/*
* heap sort 堆排序
*/

// 本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点
// 把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换
// 剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆
// 递归
public static int[] heapSort(int[] arr) {

int i;

// 将arr构成一个大顶堆
// 从 0 到 arr.length/2 ,这些都是有孩子的节点
// 没孩子的节点构造大顶堆就无意义了
for (i = arr.length / 2; i >= 0; i--) {

heapAdjust(arr, i, arr.length - 1);
}

for (i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
// 将arr[0...i-1] 重新构造成一个大顶堆
heapAdjust(arr, 0, i - 1);

}

return arr;
}

private static void heapAdjust(int[] arr, int s, int m) {

int temp, j;
temp = arr; // 指向临时(相对与root节点)的根节点

for (j = 2 * s; j <= m; j *= 2) {

// 如果右节点比左节点大,当前节点移到右节点
if (j < m && arr[j] < arr[j + 1]) {
// 指向右节点
j++;
}

// 当前的父节点大于现在指向的节点
// 不需要做任何处理
if (temp >= arr[j]) {
break;
}

// 当前的父节点小于其下的子节点
// 换位置,把这个子节点替换到父节点
// 当前这个位置,如果是叶子节点,则它应该是最小的(相对于它的祖先们)
// 这个方法目的就是交换parent与children的值,构造大根堆

// 执行到这里表明当前节点的父节点(临时根节点小于当前的节点),
// 把当前节点移到上面,换位置
// arr被覆盖无所谓,因为temp记了这个值(原来的根节点(相对的parent))
arr = arr[j];

// 现在把当前的这个元素,看做是临时的parent节点
// 为了找到此时这个元素的孩子节点,看看是否有比当前这个值还大的
// 最后s指向 当前遍历到的这个元素
s = j;
}

arr = temp;
}



/*
* 插入排序
* 思想: 扑克牌
* 从无序序列往有序子序列插入, 插入排序改进版 不足: 移动太频繁
*/

public static int[] InsertSort(int[] arr) {

// 无序序列
// 忽略首位,从1开始
for (int i = 1; i < arr.length; i++) {

int temp = arr;

int j;
// 有序序列
// 最早从0开始比对
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {

// j 后面的往后挪
arr[j + 1] = arr[j];

}
arr[j + 1] = temp;
}
return arr;
}

/*
* SHELL 希尔排序
* 插入排序改进版
*
*/
public static int[] ShellSort(int[] arr) {

// 取增量
int step = arr.length / 2;

while (step >= 1) {

// 还是忽略0位
// 0...step 1...step+1
for (int i = step; i < arr.length; i++) {

int temp = arr;

int j = 0;

// 跟插入排序的区别就在这里
for (j = i - step; j >= 0 && temp < arr[j]; j -= step) {

arr[j + step] = arr[j];
}
arr[j + step] = temp;
}

step /= 2;

}

return arr;
}







/*
*
*归并排序
*分到最细了,就剩两个数,归并,依次类推
*  本质是靠归并(有序的merge)排的序
*
*/

public static int[] mergeSort(int[] arr, int[] tempArray, int left,
int right) {

if (left < right) {

// 取分割位置
int middle = (left + right) / 2;

// 递归划分数组左序列
mergeSort(arr, tempArray, left, middle);

// 递归划分数组右序列
mergeSort(arr, tempArray, middle + 1, right);

Merge(arr, tempArray, left, middle + 1, right);
}
return arr;
}

private static void Merge(int[] arr, int[] tempArray, int left, int middle,
int right) {

int leftEnd = middle - 1;
int rightStart = middle;

// 临时数组的下标
int tempIndex = left;

// 数组合并厚的length长度
int tempLength = right - left + 1;

// 先循环两个区间段都没有结束的情况
while ((left <= leftEnd) && (rightStart <= right)) {

// 左边的比右边的小,先插入左边的
if (arr[left] < arr[rightStart]) {

tempArray[tempIndex++] = arr[left++];

} else {
tempArray[tempIndex++] = arr[rightStart++];
}
}

// 判断左序列是否结束
while (left <= leftEnd) {
tempArray[tempIndex++] = arr[left++];
}

// 判断右序列是否结束
while (rightStart <= right) {
tempArray[tempIndex++] = arr[rightStart++];
}

// 交换数据
for (int i = 0; i < tempArray.length; i++) {
arr[right] = tempArray[right];
right--;
}

}

public static void main(String[] args) {

int[] arr // = { 5, 9, 3, 7, 2, 1,6 };
= new int[100];
Random random = new Random();
random.setSeed(System.currentTimeMillis());

for (int i = 0; i < 100; i++) {
arr = random.nextInt(1000);
}

System.out.println("begin");
// quickSort(arr, 0, arr.length - 1);
// selectionSort(arr);
InsertSort(arr);

for (int e : arr) {
System.out.print(e + " ");
}

}

}
作者: Catface    时间: 2015-3-8 11:57
有本书叫做数据结构
作者: linder_qzy    时间: 2015-3-8 18:29
路文龙 发表于 2015-3-7 14:27
日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡 ...

感谢 说的很详细啊 慢慢研究吧
作者: linder_qzy    时间: 2015-3-8 18:30
gaopeng868988 发表于 2015-3-8 08:56
排序 主流七大排序，
package ds;

太多了吧 慢慢研究吧
作者: 若辰    时间: 2015-3-8 18:44
涨知识了。



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