黑马程序员技术交流社区
标题:
选择排序_逻辑分析
[打印本页]
作者:
姜姗姗
时间:
2014-4-9 22:20
标题:
选择排序_逻辑分析
package test;//选择排序
//需求:对数组{34,19,11,109,3,56}进行“选择排序”
/* 分析:
* 数组 {34,19,11,109,3,56}
* 角标 0 1 2 3 4 5
* 第一轮:0角标上的元素和1,2,3,4,5角标上的元素分别进行比较,如果0角标小,不用动,否则交换位置
* 第一轮 0---->1,2,3,4,5 0和1,2,3,4,5比较
* 第二轮 1----> 2,3,4,5 1和 2,3,4,5比较
* 第三轮 2----> 3,4,5 2和 3,4,5比较
* 第四轮 3----> 4,5 3和 4,5比较
* 第五轮 4----> 5 4和 5比较
*
该列对应外循环 横线右边 对应内循环
*
* 一共5轮,第几轮对应外循环,外循环0到4,5取不到 for(int x=0;x<arr.length-1;x++){ }
* 内循环是每一轮比较的次数,第一轮5次,第二轮4次……
* 每一轮 内循环y的初始值都不一样,所以这也就说明y的初始值不确定,不能指定具体的值,看y和行x有什么关系,y=x+1
* 那内循环y的取值呢,第一个值和最后一个都值能取到,所以是y<arr.length
* 明确1 有没有返回值?没有
* 明确2 有没有未知内容参与?有 数组 int[]
* */
public class test25 {
public static void main(String args[]){
int [] arr ={34,19,11,109,3,56};
sortArr(arr);
//System.out.println(arr);//直接打印数组是个什么东西,只能是遍历才能取出来,遍历打印
for(int i=0;i<arr.length-1;i++){
System.out.print(arr[i]+",");
}
}
public static void sortArr(int []arr){
for(int x=0;x<arr.length-1;x++){//对应有几轮
for(int y=x+1;y<arr.length;y++){//对应每轮比较几次
if(arr[x]>arr[y])//目的是x这边放最小的,如果是arr[x]>arr[y]就要交换
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}
}
复制代码
作者:
panzhenglian
时间:
2014-4-18 22:33
本帖最后由 panzhenglian 于 2014-4-18 22:36 编辑
楼主你的排序方式效率很低,在内圈每次排序之后先不要移动,记住最大数的角标位,内圈一圈走完再进行移动,我曾经实验过同样的10000个整数进行排序,如果是不记住角标位这种算法,在我的电脑上面排序需要的时间大概是是300毫秒,如果记住角标位再移动,排序需要的时间是70毫秒,而java自带的Arrays类里面的排序需要的时间是3毫秒,到现在我看不懂java中Arrays类的排序是如何做到的,
作者:
panzhenglian
时间:
2014-4-18 22:47
class MyArrays{
/**
排序方式一,效率高 :属于选择排序
*/
public static void sort1(int[] arr){
int dexMin = 0;
for(int i = 0 ; i < arr.length ; i++){
dexMin = i;
for(int j = i + 1 ; j < arr.length ; j++){
if(arr[dexMin]>arr[j]){
dexMin = j;
}
}
if(dexMin!=i){
exchangeArr(arr,dexMin,i);
}
}
}
/**
排序方式二,效率低 :属于选择排序
*/
public static void sort2(int[] arr){
for(int i = 0 ; i < arr.length ; i++){
for(int j = i + 1 ; j < arr.length ; j++){
if(arr[i]>arr[j]){
exchangeArr(arr,i,j);
}
}
}
}
/**
排序方式三,效率居中 :属于冒泡排序
*/
public static void sort3(int[] arr){
for(int i = 0 ; i < arr.length ; i ++){
for(int x = 0 , y = x + 1 ;y < arr.length - i ; x ++ , y ++){
if(arr[x]>arr[y]){
exchangeArr(arr,x,y);
}
}
}
}
/**
* 遍历数组,打印到控制台
*/
public static void printArr(int[] arr){
for(int i = 0 ; i < arr.length ; i ++){
System.out.print(arr[i]+" , ");
}
}
//私有方法,给数组提供换位服务
private static void exchangeArr(int[] arr , int a , int b){
/*
arr[a] = arr[a]^arr[b];
arr[b] = arr[a]^arr[b]; 异或换位//根据测试的时间上看,异或换位和利用第三方变量换位所需要的时间是一样的
arr[a] = arr[b]^arr[a]; */
int i = arr[a];
arr[a] = arr[b];
arr[b] = i;
}
/**
* 获取一个int类型数组;通过传入的参数决定数组的长度,该方法随机生成随机数填充到数组中
*/
public static int[] getIntArr(int len){
Random random = new Random(1245125L); //传入随机数种子,这样每次生成的10000个随机数都是一样的
int[] arr = new int[len];
for(int i = 0; i < arr.length ; i++){
arr[i] = random.nextInt(100000);
}
return arr;
}
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2