选择排序

2019/06/01 12:44
阅读数 38

  选择排序一般分为简单选择排序堆排序

  简单选择排序

  • 基本思想

      简单选择排序的第i趟是从elem[i]~elem[i-1]中选择第i小的元素,并将此元素放到elem[i]处,也就是说,简单选择排序是从为排序的序列中选择最小的关键字,接着是次小的,以此类推。

  • 复杂度分析

      最外层for循环共循环n次,内层for循环共循环n-i次,可知总比较的次数为n(n+1)/2=O(n2),可知时间复杂度为O(n2)

  • 代码实现
 1 public int[] sort3(int[] array) {
 2         // 简单选择排序
 3         for (int i = 0; i < array.length; i++) {
 4             int minIndex = i;
 5             for (int j = i; j < array.length; j++) {
 6                 if (array[j] < array[minIndex]) {
 7                     minIndex = j;
 8                 }
 9             }
10             int tmp = array[i];
11             array[i] = array[minIndex];
12             array[minIndex] = tmp;
13         }
14         return array;
15     }

 

  堆排序

  • 基本思想
  • 复杂度分析

  最坏情况下时间复杂度为O(nlogn),相对快速排序在最坏情况下的时间复杂度为O(n2),这是最大的优势,而且只占用一个用于交换记录的临时存储空间,比快速排序用栈更节约存储空间

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部