[学习交流] 排序浅谈

DAN66

本帖最后由 Deathfish 于 2015-6-11 00:09 编辑

排序作为计算机运行中的一种基本操作，常常作为编程入门示例出现在各种教材上。
下面将介绍几种不同性能的排序算法，希望大家能通过这些代码，能够体会到编程艺术的美妙。
一下示例就通过排列数组展示。
在各种排序算法中，最容易让人理解的，莫过于选择排序法
通过遍历数组中个各个元素，找出最大（最小）值，再置于数组最后（最前），从而对数组进行排序。

另一种大家都非常熟悉的是冒泡排序法
通过将数组中两相邻值做比较，前值大于后值，则将前后值位置进行替换。

接着就是相对新能较佳，内存消耗及速度性能均不错的快速排序法
选取数组中的一个值作为基准值，小于其值的置于数组前方，大于等于其值的置于数组后方，再对分割出的两个子数组做相同规则的排序

最后向大家介绍的是哈希排序的原理
将整数按位数切割成不同的数字，然后按每个位数分别比较。
相关代码如下:

class SortMethod{
/**
打印一个数组
*/
public static void listPriter(int[] arr){
for(int e: arr){
System.out.println(e);
}
}
/**
生成一个不含重复元素的从(0-n)的随机int数组
*/
public static int [] randList0 (int n)
{
int [] randNum = new int [n];
int [] unUsed = new int [n];
for (int u = 0; u < n; u++)
{
unUsed[u] = u+1;
}
for (int i = 0; i < n; i++)
{
double positionDouble = Math.random() * (n-1-i);
int position = (int) positionDouble;
randNum[i] = unUsed[position];
unUsed[position] = unUsed[n-1-i];
}
return randNum;
}
/**
生成一个包含重复元素的从(0-n)的随机int数组
*/
public static int [] randList1 (int n)
{
int [] randNum = new int[n];
// Random r = new Random();
for (int i = 0; i < n; i++)
{
double numDouble = Math.random() * (n-1-i);
int num = (int) numDouble;
randNum[i] = num;
}
return randNum;
}
/**
选择排序法
时间复杂度为O(N^2)
*/
public static int [] selectionSort(int [] unSortedArr){
int [] sortedArr = unSortedArr;
//外层循环遍历数组各元素
for (int i = 0; i < sortedArr.length ;i++){
int min =i;
//内层循环将外层循环所遍历到的元素和数组中其它为排序的元素进行大小比较
for(int j =i ; j< sortedArr.length;j ++){
if (sortedArr[min] > sortedArr[j]){
min = j;
}
}
//比较后得出未排序数组中的最小值，将其写入到排序数组的前部
int temp = sortedArr[i];
sortedArr[i] = sortedArr[min];
sortedArr[min] = temp;
}
return sortedArr;
}
/**
冒泡排序法
时间复杂度为O(N^2)
*/
public static int [] bubbleSort(int [] unSortedArr){
//外层循环遍历数组各元素
for (int i = 0; i < unSortedArr.length ; i++ ){
//内层循环将外层循环所遍历到的元素和其相邻的后一位数组进行大小比较
for(int j = 0; j < unSortedArr.length-i-1; j++){
if(unSortedArr[j]>unSortedArr[j+1]){
//比较后，相对较大的元素置于相对靠后的位置
int temp = unSortedArr[j];
unSortedArr[j] = unSortedArr[j+1];
unSortedArr[j+1] = temp;
}
}
}
return unSortedArr;
}
/**
快速排序法
时间复杂度为O(NlogN)
*/
public static int [] QuickSort(int [] unSortedArr, int startIndex, int endIndex){
//先选取基准值为最后一个元素的大小。同时设置数组排序的起始及终止角标
int pivot = endIndex;
int l = startIndex;
int h = endIndex;
while(l<h){
//遍历时末端角标往前移一位
h--;
//通过while循环从数组后端 h 至数组前端 l 遍历，若被遍历的元素小于基准值，
// 则将其移动到数组前端，同时前端 l 角标增一位。
while(l<h&&unSortedArr[pivot]>unSortedArr[h]){
int temp0 = unSortedArr[l];
unSortedArr[l] = unSortedArr[h];
unSortedArr[h] = temp0;
l++;
}
}
// 循环遍历完后 l=h ，还剩下角标为 l 的元素未和基准值比对过大小。
// 同时基准值位于数组最末端，这时我们需要将它移动到数组中间。
if(unSortedArr[pivot]>unSortedArr[l]){
int temp1 = unSortedArr[l+1];
unSortedArr[l+1] = unSortedArr[pivot];
unSortedArr[pivot] = temp1;
pivot = l+1;
}else{
int temp2 = unSortedArr[l];
unSortedArr[l] = unSortedArr[pivot];
unSortedArr[pivot] = temp2;
pivot = l;
}
// 最后将大于基准值与小于基准值的两个数组部分通过递归进行传递排序
if(pivot-1>startIndex)
QuickSort(unSortedArr,startIndex,pivot-1);
if(endIndex>pivot+1)
QuickSort(unSortedArr,pivot+1,endIndex);
return unSortedArr;
}
/**
哈希排序法(模拟)
先找出数组中的最大值和最小值，创建一个max-min长度的临时寄存数组，
遍历待排序数组，将遍历到的数组元素放入下标与其值相等的临时寄存数组中(临时寄存数组对应下标的元素的值+1)，
待遍历完原数组后，对临时寄存数组进行遍历。若数组中值为n，则说明原数组中有n个大小为数组下标+min的元素。
将这些元素按顺序添加入一个新数组中，这个新数组就是一个排序好的数组。
时间复杂度为O(N)
*/
public static int [] hashSort(int [] unSortedArr){
int max = unSortedArr[0];
int min = unSortedArr[0];
int [] sortedArr = new int [unSortedArr.length];
// 通过for循环找到最大值和最小值
for (int i =0; i< unSortedArr.length; i++){
if(unSortedArr[i]>max)
max = unSortedArr[i];
if(unSortedArr[i]<min)
min = unSortedArr[i];
}
// 定义储存元素的临时数组，数组的大小为最大值至最小值的范围
int [] sortTemp = new int[max-min+1];
// 通过for循环遍历未排序的原数组，将遍历到的数组元素放入下标与其值相等的临时寄存数组中
for(int i = 0; i<unSortedArr.length; i++){
sortTemp[unSortedArr[i]-min] += 1;
}
//定义数组指针
int index = 0;
//通过for循环将临时数组中的元素顺序取出，存入新的数组中，既是排序好的数组
for(int i = 0; i<sortTemp.length; i++){
for(int j = 0; j<sortTemp[i]; j++){
sortedArr[index] = i+min;
index++;
}
}
return sortedArr;
}
}

复制代码

对于不同排序算法的运行效率结果如下：

测试代码见一楼。

Deathfish · Deathfish

public class SortMethodTest{
public static void main(String [] args){
int n = 10000000;
long timeStart,timeEnd ;
int[] randomList = SortMethod.randList1(n);
System.out.println("无序数组的大小为："+n);
timeStart = System.currentTimeMillis();
int [] sortedList0 = SortMethod.selectionSort(randomList);
timeEnd = System.currentTimeMillis();
// SortMethod.listPriter(sortedList0);
System.out.println("selectionSort选择排序排序时间 time : " + (timeEnd - timeStart) + "毫秒 ");
timeStart = System.currentTimeMillis();
int [] sortedList1 = SortMethod.bubbleSort(randomList);
timeEnd = System.currentTimeMillis();
// SortMethod.listPriter(sortedList1);
System.out.println("bubbleSort冒泡排序排序时间 time : " + (timeEnd - timeStart) + "毫秒 ");
timeStart = System.currentTimeMillis();
int [] sortedList2 = SortMethod.QuickSort(randomList,0,randomList.length-1);
timeEnd = System.currentTimeMillis();
// SortMethod.listPriter(sortedList2);
System.out.println("QuickSort快速排序排序时间 time : " + (timeEnd - timeStart) + "毫秒 ");
timeStart = System.currentTimeMillis();
int [] sortedList3 = SortMethod.hashSort(randomList);
timeEnd = System.currentTimeMillis();
// SortMethod.listPriter(sortedList3);
System.out.println("hashSort哈希排序排序时间 time : " + (timeEnd - timeStart) + "毫秒 ");
}
}

复制代码

小骆驼 · 小骆驼

赞一个，不错，好好学习下

DAN66 · DAN66

赞一个

q757571446 · q757571446

赞一个，好帖子长见识了/

集体烧书 · 集体烧书

林宏大神，膜拜啊

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 排序浅谈

评分

5 个回复