选择排序展示(java)

简介 (以下为百度)选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

package algorithm;

/**

 * 时间:2019 8 24 

 * 作者latefly

 * 功能:一个选择排序算法的一个展示

 * 

 */

import java.text.SimpleDateFormat;

import java.util.Date;


public class SelectSort {

static int counter = 0;

static int arrSize = 80000;// 此处实测大概是2s-3s之间


public static void main(String[] args) {


// 产生随机数

int arr[] = new int[arrSize];

for (int i = 0; i < arrSize; i++) {

arr[i] = (int) (Math.random() * 8000000);

}

// System.out.println(Arrays.toString(arr));

Date dateStart = new Date();

SimpleDateFormat format = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss");

String start = format.format(dateStart);

System.out.println("开始时间:" + start);


// 测试数组

rectifySelectSort(arr);


Date endStart = new Date();

String end = format.format(endStart);

System.out.println("结束时间:" + end);

// System.out.println(Arrays.toString(arr));

// TODO Auto-generated method stub


}


public static void baseSelectSort(int arr[]) {

int min;

int minIndex;

int counter;

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

// 每次选择一个最小的然后交换顺序

counter = i;

min = arr[i];

minIndex = i;

while (counter < arr.length) {

// 找到小的然后交换

if (arr[counter] < min) {

min = arr[counter];

minIndex = counter;

}


counter++;

}

arr[minIndex] = arr[i];

arr[i] = min;

}

}


// 改进以后的算法

public static void rectifySelectSort(int arr[]) {

int min;

int minIndex;

int counter;

boolean ischange = false;

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

// 每次选择一个最小的然后交换顺序

counter = i;

min = arr[i];

minIndex = i;

ischange = false;

while (counter < arr.length) {

// 找到小的然后交换

if (arr[counter] < min) {

min = arr[counter];

minIndex = counter;

ischange = true;

}


counter++;

}

if (ischange) {

arr[minIndex] = arr[i];

arr[i] = min;

}


}

}

}

image.png


可以明显的看到选择排序比冒泡的速度要快,这里80000个数据用了3s(非精确时间)


文章评论

Top