博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
2.选择排序
阅读量:802 次
发布时间:2019-03-25

本文共 1583 字,大约阅读时间需要 5 分钟。

选择排序的时间复杂度是O(N^2)额外空间复杂度O(1)

在这里插入图片描述

具体实现过程请观看

牛客老师做法
public static void SelectSort(int[] arr) {
if(arr == null || arr.length < 2) {
return; } for(int i=0; i
< arr[midIndex] ? j : midIndex; } swap(arr, i, midIndex); } } static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
以往自己的写法
public static void SelectSort2(int[] arr) {
if(arr == null || arr.length < 2) {
return; } for(int i=0; i
反思:

自己的做法是每一趟比较中每比较一个元素就交换

这样就浪费了大量的资源和时间,牛客老师的做法是用一个局部变量记录每趟比较中最小元素的下标
在每趟比较中更新最小元素的下标,老师的效率高

完整代码
package yzy.algorithm;import java.util.Arrays;public class testSelectSort {
public static void main(String[] args) {
int[] values = new int[10]; for(int i=0;i<10;++i) {
values[i] = (int) (10* Math.random()); } System.out.println(Arrays.toString(values)); SelectSort(values); System.out.println(Arrays.toString(values)); int[] values2 = new int[10]; for(int i=0;i<10;++i) {
values2[i] = (int) (10* Math.random()); } System.out.println(Arrays.toString(values2)); SelectSort2(values2); System.out.println(Arrays.toString(values2)); } //牛客老师做法 public static void SelectSort(int[] arr) {
if(arr == null || arr.length < 2) {
return; } for(int i=0; i
< arr[midIndex] ? j : midIndex; } swap(arr, i, midIndex); } } public static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } //以往自己的写法 public static void SelectSort2(int[] arr) {
if(arr == null || arr.length < 2) {
return; } for(int i=0; i

转载地址:http://sldyk.baihongyu.com/

你可能感兴趣的文章