求排序法

看看大bug的博客吧，他比较喜欢算法
http://blog.csdn.net/bigbug9002

JAVA四种基本排序,包括冒泡法,插入法,选择法,SHELL排序法.其中选择法是冒泡法的改进,SHELL排序法是插入法的改进.所以从根本上来说可以归纳为两种不同的排序方法:即:插入法＆冒泡法
一、插入法:遍历排序集合，每到一个元素时，都要将这个元素与所有它之前的元素遍历比较一遍，让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。交换是相邻遍历移动，双重循环控制实现.这种排序法属于地头蛇类型,在我的地牌上我要把所有的东西按一定的顺序规整,过来一个,规整一个.处理代码如下:
public void sort(int[] data) {
int temp;
for(int i=1; i〈data.length; i++){
for(int j=i; (j〉0)&&(data[j]〉data[j-1]); j--){
temp=date[j]; data[j]=data[j-1]; data[j-1]=temp;
}
}
}
二、冒泡法:比较容易，它的内层循环保证遍历一次后，集合中最小（大）元素出现在它的正确位置，下一次就是次小元素该方法在集合分布的各种情况下交换移动的次数基本不变，属于最慢的一种排序。实现也是双重循环控制。这种排序法属于过江龙,就是要找到极端,但是过奖龙也有大哥,二哥等,所以他们只能是大哥挑了二哥挑.处理代码如下:
public static int [] maopao(int[] data) {
int temp; for(int i=0; i〈data.length-1; i++){
for(int j=i+1; j〈data.length; j++){
if(data〈data[j]){
temp=data; data=data[j]; data[j]=temp;
}
}
}
return data;
}
三、选择法:该方法只是通过遍历集合记录最小（大）元素的位置，一次遍历完后，再进行交换位置操作，类似冒泡，但在比较过程中，不进行交换操作，只记录元素位置。一次遍历只进行一次交换操作。这个对与交换次序比较费时的元素比较适合。这种排序法比冒泡法要城府要深的多,我先记住极端数据,待遍历数据完了之后,我再处理,不像冒泡法那样只要比自己极端一点的就要处理,选择法只处理本身范围内的最极端数据.
public static void xuanze(int[] data) {
int temp;
for (int i = 0; i 〈 data.length; i++) {
int lowIndex = i;
for (int j = data.length - 1; j 〉 i; j--) {
if (data[j] 〉 data[lowIndex]) {
lowIndex = j;
}
}
temp=data;
data=data[lowIndex];
data[lowIndex]=temp;
}
}
四、Shell排序：它是对插入排序的一种改进，是考虑将集合元素按照一定的基数划分成组去排序，让每一组在局部范围内先排成基本有序，最后在进行一次所有元素的插入排序。
public void sort(int[] data) {
for(int i=data.length/2; i〉2; i/=2){
for(int j=0; j〈i; j++){
insertSort(data,j,i);
}
}
insertSort(data,0,1);
}
private void insertSort(int[] data, int start, int inc) {
int temp;
for(int i=start+inc; i〈data.length; i+=inc){
for(int j=i; (j〉=inc)&&(data[j]〈data[j-inc]); j-=inc){
temp=data[j];
data[j]=data[j-inc]data[j-inc]=temp;
}
}
}

public class SortUtil {

 /**
 * 冒泡排序 Bubble Sort
 * 
 * 原理: 比较n轮，每一轮都把最大元素移动到数组后端。
 *
 * @return
 */
 public int[] bubbleSort(int[] result) {
 int ARRAYSIZE = result.length;
 for (int i = 0; i < ARRAYSIZE; i++) {
 for (int j = i + 1; j < ARRAYSIZE; j++) {
 if (result[i] > result[j]) {
 // 交换
 swap(result, i, j);
 }
 }
 }

 return result;
 }

 /**
 * 插入排序 Insert Sort
 * 
 * 原理：从第二个元素开始，因为左侧的数组为排序后的数组，只要将当前元素插入到左侧数组的适当位置，就能保持数组为有序
 * 然后处理第三个元素...直到最后一个元素
 *
 * @return
 */
 public int[] insertSort(int[] result) {
 int ARRAYSIZE = result.length;
 for (int i = 1; i < ARRAYSIZE; i++) {
 for (int j = i; j > 0 && result[j] < result[j - 1]; j--) {
 swap(result, j, j - 1);

 }
 }

 return result;
 }

 /**
 * 折半搜索插入排序 BinarySearchThenInsert Sort
 * 
 * 原理与插入排序类似，不同点在于寻找插入位置的时候，采取的是折半查找方法
 *
 * @return
 */
 public int[] binsertSort(int[] result) {
 int ARRAYSIZE = result.length;
 for (int i = 1; i < ARRAYSIZE; i++) {
 if (result[i] < result[0]) {
 int temp = result[i];
 for (int j = i - 1; j >= 0; j--) {
 result[j + 1] = result[j];

 }
 result[0] = temp;

 } else if (result[i] < result[i - 1]) {
 int larrange = 0;
 int rarrange = i - 1;
 while (rarrange - larrange > 1) {
 int p = (rarrange + larrange + 1) / 2;
 if (result[i] < result[p]) {
 rarrange = p;
 } else {
 larrange = p;
 }

 }
 int temp = result[i];
 for (int j = i - 1; j >= larrange + 1; j--) {
 result[j + 1] = result[j];

 }
 result[larrange + 1] = temp;

 }
 }

 return result;
 }

 /**
 * 堆排序 Heap Sort
 * 
 * 原理: 利用了堆的易调整的特点来进行的一种选择排序。以大顶堆为例，什么是大顶堆？
 * 大顶堆的逻辑结构是一颗完全二叉树，[把满二叉树最后一层右侧的一些叶子摘掉] 假设其高度为h，则元素个数介于 1 + 2 + ... +
 * exp(2, h - 2) ~ 1 + 2 + ... + exp(2, h -1)之间符合如下定义为大顶堆：(此定义基于大顶堆的顺序存储结构)
 * for (int i = array.length - 1; i > 0; i --) { 任意 array[i] <= array[(i -
 * 1)/2]; } (还有一种是小顶堆，不同的只是比较时候的大于号方向不同)。容易想到，当堆顶元素(MaxValue)被替换后，
 * 至多只要在双亲和子节点间进行h（大顶堆的高度） - 1次交换， (参照交换算法可以发现比较次数一般来说是交换次数的2~3倍，也不算多)
 * 就可以形成新的大顶堆。由此大大提高了排序效率。
 *
 * @return
 */
 public int[] heapSort(int[] result) {

 // 初始化无序数组为大顶堆
 for (int i = result.length - 2; i >= 0; i--) {
 adjustHeap(result, i, result.length - 1);
 }

 // 将最大值元素交换至数组末端，并调整前端为大顶堆，循环直至前端只剩下一个元素
 for (int i = result.length - 1; i > 0; i--) {
 swap(result, 0, i);
 adjustHeap(result, 0, i - 1);
 }

 return result;
 }

 /**
 * 将除顶(不确定是否满足大顶堆条件)外，左子树和右子树都为一个堆的数组调整为大顶堆
 *
 * @param array
 * 待调整数组
 * @param from
 * 顶的指针
 * @param to
 * 调整的末端(就是调整array[from]...array[to]这一段为一个大顶堆)
 */
 private void adjustHeap(int[] array, int from, int to) {
 int i = 0;
 // 比较节省比较次数的方法，只要比较到比其左右子树的根结点的值都大，就可以return了
 while (from + 2 * i + 2 <= to) {
 if (array[from + i] < array[from + 2 * i + 1]
 || array[from + i] < array[from + 2 * i + 2]) {
 if (array[from + 2 * i + 1] > array[from + 2 * i + 2]) {
 swap(array, from + i, from + 2 * i + 1);
 i += i + 1;
 } else {
 swap(array, from + i, from + 2 * i + 2);
 i += i + 2;
 }

 } else {
 return;
 }
 }
 if (from + 2 * i + 1 == to && array[from + i] < array[from + 2 * i + 1]) {
 // 有时会出现仅存在左子树的情况(左子树为调整数组的最后一个元素)
 swap(array, from + i, from + 2 * i + 1);

 }
 }

接上 /**
 * 快速排序 Quick Sort
 * 
 * 原理：选择数组中的一个元素作为标准，将所有比标准小的元素放到左边，所有比标准大的元素放到右边。并对左边和右边的元素做一样的快速排序过程。
 *
 * @return
 */
 public int[] quickSort(int[] result) {
 quick(result, 0, result.length - 1);
 return result;
 }

 /**
 * 选择数组中的一个元素作为标准，将所有比标准小的元素放到左边，所有比标准大的元素放到右边。并对左边和右边的元素做一样的快速排序过程。
 *
 * @param array
 * @param startIndex
 * @param endIndex
 */
 private void quick(int[] array, int startIndex, int endIndex) {
 int pIndex = startIndex;
 for (int i = startIndex + 1; i <= endIndex; i++) {
 if (array[i] < array[pIndex]) {
 int temp = array[i];
 for (int j = i; j > pIndex; j--) {
 array[j] = array[j - 1];
 }
 array[pIndex] = temp;
 pIndex++;
 }

 }
 if (pIndex - startIndex > 1) {
 quick(array, startIndex, pIndex - 1);
 }
 if (endIndex - pIndex > 1) {
 quick(array, pIndex + 1, endIndex);
 }
 }

 /**
 * 归并排序 Merge Sort
 * 
 * 原理：分治。将数组分为左，右两部分，首先将数组分为左右两部分，分别进行归并排序，然后合并左右两部分的排序结果就构成了一个有序数组。
 *
 * @return
 */
 public int[] mergeSort(int[] result) {

 mergeR(result, 0, result.length - 1);

 return result;
 }

 /**
 * 递归对数组进行归并排序
 *
 * @param array
 * @param startIndex
 * @param endIndex
 */
 private void mergeR(int[] array, int startIndex, int endIndex) {
 if (startIndex < endIndex) {
 int mid = (startIndex + endIndex) / 2;
 // 对包括中点在内的左侧数组区间进行归并排序
 mergeR(array, startIndex, mid);
 // 对中点之后的右侧数组区间进行归并排序
 mergeR(array, mid + 1, endIndex);
 // 合并左和右两个独立的有序区间为一个有序区间
 merge(array, startIndex, mid, endIndex);
 }
 }

 /**
 * 将array数组的两个有序区间array[startIndex]...array[midIndex] 和array[midIndex +
 * 1]...array[endIndex]合并为一个有序区间 array[startIndex]...array[endIndex]
 *
 * @param array
 * @param startIndex
 * @param midIndex
 * @param endIndex
 */
 private void merge(int[] array, int startIndex, int midIndex, int endIndex) {
 int[] resultTemp = new int[endIndex - startIndex + 1];

 int pr = 0;
 int p1 = startIndex;
 int p2 = midIndex + 1;
 while (p1 <= midIndex || p2 <= endIndex) {
 if (p1 == midIndex + 1) {
 while (p2 <= endIndex) {
 resultTemp[pr++] = array[p2++];

 }
 } else if (p2 == endIndex + 1) {
 while (p1 <= midIndex) {
 resultTemp[pr++] = array[p1++];

 }
 } else if (array[p1] <= array[p2]) {
 resultTemp[pr++] = array[p1++];

 } else {
 resultTemp[pr++] = array[p2++];

 }
 }
 for (p1 = startIndex, p2 = 0; p1 <= endIndex; p1++, p2++) {
 array[p1] = resultTemp[p2];

 }
 }

 /**
 * 希尔排序 Shell Sort
 * 
 * 原理：分别以数组大小的1/2,1/4,1/8....1的作为步伐d，将array[i],array[i + d],array[i +
 * 2d]....array[i + nd]看作一个数组进行排序，与插入排序相比，因为可以更有效的消除逆序，因此交换次数是很少的，
 * 缺点是比较次数过多
 *
 * @return
 */
 public int[] shellSort(int[] result) {
 int ARRAYSIZE = result.length;
 for (int d = ARRAYSIZE / 2; d > 0; d = d / 2) {
 // print(result);
 for (int i = d; i < ARRAYSIZE; i++) {
 for (int j = i; j >= d; j = j - d) {
 if (result[j] < result[j - d]) {
 swap(result, j, j - d);
 }

 }
 }
 }

 return result;
 }

 /**
 * 简单选择排序 SimpleSelection Sort
 * 
 * 原理：每遍历未排序部分一次都选出一个最小值，并将最小值元素移动到数组前端
 *
 * @return
 */
 public int[] simpleSelectionSort(int[] result) {

 // 重复此过程：选取最小值，并将其交换至数组前端
 int minIndex = 0;
 for (int i = 0; i < result.length; i++) {
 minIndex = i;
 for (int j = i + 1; j < result.length; j++) {
 if (result[j] < result[minIndex]) {
 minIndex = j;
 }

 }
 swap(result, minIndex, i);
 }

 return result;
 }

 /**
 * 交换元素
 */
 private void swap(int[] arr, int i, int j) {
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }

 }

public class Sort { //冒泡排序
public void bubbleSort(int[] src){
int time = src.length-1;
boolean breakFlag = true;
while(time>0){
for(int j = 0; j<time; j++){
if(src[j]>src[j+1]){
int tmp = src[j+1];
src[j+1] = src[j];
src[j] = tmp;
breakFlag = false;
}
}
if(breakFlag){
break;//顺序已经好了这不用在进行排序了
}
time--;
breakFlag = true;
}
//显示结果
for(int value : src){
System.out.print(value + " ");
}
System.out.println();
}
//选择排序
public void selectionSort(int[] src){
int n=src.length;
int k = 0;
for(int i=0;i<n;i++){
k = i;
for(int j=i+1;j<n;j++){
if(src[k]>src[j]){
k = j;
}
}
int tmp = src[k];
src[k] = src[i];
src[i] = tmp;
}
//显示结果
for(int value : src){
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args){
Sort app = new Sort();
int[] value = {9,8,7,6,5,4,3,2,1,0};
System.out.print("排序前的结果");
//元数据
for(int v : value){
System.out.print(v + " ");
}
System.out.print("\r\n冒泡排序后的结果");
app.bubbleSort(value);
System.out.print("选择排序后的结果");
app.selectionSort(value);
}
}

解决方案 »