盒子
盒子
文章目录
  1. 详细步骤
  2. 实现
  3. 总结

算法(一)直接选择排序

直接选择排序,整体思想是将数据分成两个区域,有序区无序区。排序的时候是每次从无序区中选择出最小的数,然后插入到有序区中的最末尾,从而形成更大的有序区。直到无序区中的数为零,结束排序。

详细步骤

假设排序数组为a[0…n-1];

  1. 首先有序区中的个数为0,令i = 0。从无序区中选择最小的数,加入到有序区a[i]中。使得有序区a[0..i],无序区a[i...n-1]
  2. 完成后 i++ ,然后继续前面的步骤,直到 i = n-1 为止。使得全部数都在有序区中。

所以根据上面的思想步骤就能很容易的写出实现代码了

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void selectSort(int[] arr) {
int temp;
int mid;
for (int i = 0; i < arr.length - 1; i++) {
mid = i;//关键数
for (int j = mid + 1; j < arr.length; j++) {
if (arr[mid] > arr[j])//找到最小值
mid = j;
}
if (mid != i) {//不等于关键数则交换
temp = arr[mid];
arr[mid] = arr[i];
arr[i] = temp;
}
}
}

总结

该排序为不稳定排序,首先说明何为稳定排序:在排序结束后如果排序中相同大小的数与排序前的相对位置相同(即前后位置不变),则称为稳定排序 直接选择排序我们很容易发现,如果排序数组为a[11,11,2]在进行第一趟排序之后第一个112交换位置使得原来前面的11排序到后面的11之后,所以直接选择排序为不稳定排序。同时它的时间复杂度为O(n^2)

转载请指明出处 idisfkj博客:https://idisfkj.github.io

支持一下
赞赏是一门艺术