微信号:grzlwx

介绍:光荣之路官方资讯

八大种必知排序算法(一) 冒泡排序、快速排序 (续)

2015-08-30 21:37 光荣之路


代码实现如下:

1.查找中轴(最低位作为中轴)所在位置

/**
* 查找出中轴(默认是最低位low)的在numbers数组排序后所在位置
*
* @param numbers 带查找数组
* @param low 开始位置
* @param high 结束位置
* @return 中轴所在位置
*/
public static int getMiddle(int[] numbers, int low,int high)
{
int temp = numbers[low]; //数组的第一个作为中轴
while(low < high)
{
while(low < high && numbers[high] > temp)
{
high--;
}
numbers[low] = numbers[high];//比中轴小的记录移到低端
while(low < high && numbers[low] < temp)
{
low++;
}
numbers[high] = numbers[low] ; //比中轴大的记录移到高端
}
numbers[low] = temp ; //中轴记录到尾
return low ; // 返回中轴的位置
}


2、 递归形式的分治排序算法:

/**
*
* @param numbers 带排序数组
* @param low 开始位置
* @param high 结束位置
*/
public static void quickSort(int[] numbers,int low,int high)
{
if(low < high)
{
  int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
  quickSort(numbers, low, middle-1); //对低字段表进行递归排序
  quickSort(numbers, middle+1, high); //对高字段表进行递归排序
}

}


3、快速排序提供方法调用

/**
* 快速排序
* @param numbers 带排序数组
*/
public static void quick(int[] numbers)
{
if(numbers.length > 0) //查看数组是否为空
{
quickSort(numbers, 0, numbers.length-1);
}
}


分析:

  快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。



方法测试

打印函数:

public static void printArr(int[] numbers)
{
for(int i = 0 ; i < numbers.length ; i ++ )
{
System.out.print(numbers[i] + ",");
}
System.out.println("");
}

测试:

public static void main(String[] args)
{
int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
System.out.print("排序前:");
printArr(numbers);

bubbleSort(numbers);
System.out.print("冒泡排序后:");
printArr(numbers);


quick(numbers);
System.out.print("快速排序后:");
printArr(numbers);
}

结果:

排序前:10,20,15,0,6,7,2,1,-5,55,
冒泡排序后:-5,0,1,2,6,7,10,15,20,55,
快速排序后:-5,0,1,2,6,7,10,15,20,55,

选择排序、插入排序、希尔排序可查看:http://www.cnblogs.com/0201zcr/p/4764427.html

归并排序、堆排序可查看:http://www.cnblogs.com/0201zcr/p/4764705.html

  

  致谢:感谢您的耐心阅读!(完)

(作者:WhyWin 来源:http://www.cnblogs.com/0201zcr/p/4763806.html)


  
             
  
             
  
             
  
            
  
            
  
            
  
            
  
            
  
            
  
            
  
            
  
            
  
            

一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!

光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499


 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 让 Alfred 支持拼音搜索 MongoDB · 特性分析 · MMAPv1 存储引擎原理 SAP与IBM优势互补 推出业界领先的人力资源解决方案 Python解析svn密码配置文件 【混合云全能馆】COSN技术一瞥——构建混合云的软件基石