选择排序的思想:选出最小的一个和第一个位置交换,选出其次小的和第二个位置交换 ……
直到从第N个和第N-1个元素中选出最小的放在第N-1个位置。
a) 原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。也就是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。(这里只介绍常用的简单选择排序)
b) 简单选择排序的基本思想:给定数组:int[] arr={里面n个数据};第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换;第2趟,在待排序数据arr[2]~arr[n]中选出最小的数据,将它与r[2]交换;以此类推,第i趟在待排序数据arr[i]~arr[n]中选出最小的数据,将它与r[i]交换,直到全部排序完成。
c) 举例:数组 int[] arr={5,2,8,4,9,1};
-------------------------------------------------------
第一趟排序: 原始数据:5 2 8 4 9 1
最小数据1,把1放在首位,也就是1和5互换位置,
排序结果:1 2 8 4 9 5
-------------------------------------------------------
第二趟排序:
第1以外的数据{2 8 4 9 5}进行比较,2最小,
排序结果:1 2 8 4 9 5
-------------------------------------------------------
第三趟排序:
除1、2以外的数据{8 4 9 5}进行比较,4最小,8和4交换
排序结果:1 2 4 8 9 5
-------------------------------------------------------
第四趟排序:
除第1、2、4以外的其他数据{8 9 5}进行比较,5最小,8和5交换
排序结果:1 2 4 5 9 8
-------------------------------------------------------
第五趟排序:
除第1、2、4、5以外的其他数据{9 8}进行比较,8最小,8和9交换
排序结果:1 2 4 5 8 9
-------------------------------------------------------
注:每一趟排序获得最小数的方法:for循环进行比较,定义一个第三个变量temp,首先前两个数比较,把较小的数放在temp中,然后用temp再去跟剩下的数据比较,如果出现比temp小的数据,就用它代替temp中原有的数据。具体参照后面的代码示例,相信你在学排序之前已经学过for循环语句了,这样的话,这里理解起来就特别容易了。
//选择排序 public class SelectionSort { public static void main(String[] args) { int[] arr={1,3,2,45,65,33,12}; //选择排序的优化 for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序 int k = i; for(int j = k + 1; j < arr.length; j++){// 选最小的记录 if(arr[j] < arr[k]){ k = j; //记下目前找到的最小值所在的位置 } } //在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换 if(i != k){ //交换a[i]和a[k] int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } } } }
选择排序的复杂度分析。第一次内循环比较N - 1次,然后是N-2次,N-3次,……,最后一次内循环比较1次。共比较的次数是 (N - 1) + (N - 2) + ... + 1,求等差数列和,得 (N - 1 + 1)* N / 2 = N^2 / 2。
舍去最高项系数,其时间复杂度为 O(N^2)。
虽然选择排序和冒泡排序的时间复杂度一样,但实际上,选择排序进行的交换操作很少,最多会发生 N - 1次交换。
而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲,交换排序的性能略优于冒泡排序。
优化版本:
根据上边的分析,如果在每一次查找最小值的时候,也可以找到一个最大值,然后将两者分别放在它们应该出现的位置,这样遍历的次数就比较少了,下边给出代码实现:
void SelectSort(vector<int>& a) { int left = 0; int right = a.size() - 1; int min = left;//存储最小值的下标 int max = left;//存储最大值的下标 while(left <= right) { min = left; max = left; for(int i = left; i <= right; ++i) { if(a[i] < a[min]) { min = i; } if(a[i] > a[max]) { max = i; } } swap(a[left],a[min]); if(left == max) max = min; swap(a[right],a[max]); ++left; --right; } }
这样总共遍历的次数比起前边的一般版本就会减少一半,时间复杂度是O(N/2 * N /2)还是O(N*N)。但是,代码中,第一次交换结束后,如果left那个位置原本放置的就是最大数,交换之后,需要将最大数的下标还原。
需要注意的是,每次记住的最小值或者最大值的下标,这样方便进行交换。
2、堆排序
完全二叉树
若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。
堆
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:
同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:
大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
ok,了解了这些定义。接下来,我们来看看堆排序的基本思想及基本步骤:
堆排序基本思想及步骤
堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
再简单总结下堆排序的基本思路:
a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
package com.test; import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = { 4, 6, 8, 5, 9}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr) { // 1.构建大顶堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { // 从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr, i, arr.length); } // 2.调整堆结构+交换堆顶元素与末尾元素 for (int j = arr.length - 1; j > 0; j--) { swap(arr, 0, j);// 将堆顶元素与末尾元素进行交换 adjustHeap(arr, 0, j);// 重新对堆进行调整 } } /** * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上) * * 从最后一个非叶子节点(a.length/2 - 1)开始,处理完后,K为其值大的叶子节点; * 此时K下面没有叶子节点,所以要依次往最后一个非叶子节点的根节点去调整置换 * @param arr * @param i * @param length */ public static void adjustHeap(int[] arr, int i, int length) { int temp = arr[i];// 先取出当前元素i //k = k*2+1是循环调整当前K节点的下面的堆 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {// 从i结点的左子结点开始,也就是2i+1处开始 if (k + 1 < length && arr[k] < arr[k + 1]) {// 如果左子结点小于右子结点,k指向右子结点 k++; } if (arr[k] > temp) {// 如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) //arr[i] = arr[k]; swap(arr,i,k); i = k; } else { break; } } //arr[i] = temp;// 将temp值放到最终的位置 } /** * 交换元素 * * @param arr * @param a * @param b */ public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
堆排序是一种选择排序,整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n),在交换并重建堆的过程中,需交换n-1次,而重建堆的过程中,根据完全二叉树的性质,[log2(n-1),log2(n-2)...1]逐步递减,近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
相关推荐
直接插入排序,选择排序,冒泡排序,堆排序等的比较!及具体代码实现
这个是整理好了的,各种排序方式,喜欢的同学可以看下,对于初学的人很有帮助
不稳定的排序算法:快速排序、希尔排序、堆排序、选择排序(简简记记::快快些些选选堆堆) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 当n较大,则应采用时间复杂度为O(nlogn)的...
#include #include #include ... //选择 //insert_sort(a, 10); //插入 //quick_sort(a, 0, N-1); //快速 //merger_sort(a, 0, N-1); //归并 heap_sort(a, N); //堆 print_array(a, N); return 0; }
大学课程、数据结构、C代码、 以下问题要求统一在一个大程序里解决。 1折半插入排序 2冒泡排序 3快速排序 4简单选择排序 5归并排序 6堆排序
2.采用的排序方法不低于4种,取自:冒泡排序、直接插入排序、希尔排序、快速排序、选择排序、堆排序、归并排序等。 3.分别计算每种算法排序所花费的时间,并简要对比分析。 4.程序最好有菜单供选,有信息提示。 解压...
不稳定的排序算法:快速排序、希尔排序、堆排序、选择排序(简记:快些选堆)所需辅助空间最多:归并排序。所需辅助空间最少:堆排序。平均速度最快:快速排序。当n较大,则应采用时间复杂度为O(nlogn)的排序方法:...
f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; 具体要求如下: a) 测试数据分出三类:正序,逆序,随机数据; b) 对于这三类数据,比较上述排序算法中的关键字的比较次数和移动次数; c) 对于这三类...
(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100(原始数据不少于100 ,可以用1000,这样方便测试出运行时间),表中数据随机产生,至少用5组不同...
(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100,表中数据随机产生,至少用5组不同数据作比较,比较指标有:关键字参加比较次数和关键字的移动次数...
(1)对以下6种常用的内部排序算法进行比较z起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于1005其中的数据要用伪随机数产生程序产生:至少要用5组不同的输入数据作比较...
题目一:在堆排序中,元素下标从0开始。则对于下标为i的元素,其左、右孩子的下标分别为: A. 2i-1, 2i B. 2i, 2i+1 C. 2i+1, 2i+2 D. 2i+2, 2i+3 选C 0的左子1右子2,代进去,只有C对。 题目二:对N个记录进行堆...
常用排序算法总结 各种内排序方法的选择 对元素个数较多的排序,可以选快速排序、堆排序、归并排序,元素个数较少时,可以选简单的排序方法。
该文档包含了七大排序,冒泡,选择,插入,快排,希尔,归并和最小堆排序,绝对有用,对面试很有帮助
一、实验目的 1、掌握排序的不同方法,并能用高级语言实现排序算法 二、实验内容 2、实现快速和堆排序算法。(可选作)
【基本要求】(1)对各种内部排序算法进行比较,包括(书中没有提到请自行查阅课外资料):冒泡排序,插入排序,选择排序,计数排序,快速排序,归并排序,希尔排序,基数排序,堆排序。 (2)待排序表的表...
排序实现 内部排序的C ++实现。 撰写人: 气泡排序 按计数排序 通过二进制堆排序 按插入排序 合并排序 快速分类 按选择排序 振动筛分选 壳排序(随着距离的减小) 用二叉搜索树排序
选择排序比较好理解,好像是在一堆大小不一的球中进行选择(以从小到大,先选最小球为例): 1. 选择一个基准球 2. 将基准球和余下的球进行一一比较,如果比基准球小,则进行交换 3. 第一轮过后获得最小的球 4. 在挑...
(4)堆排序O(n);无论时间、空间;数据各方面最好;平均性能不如快排 (5)稳定:直插、冒泡、归并、基数 (6)若n较小;采用直插和简单选择;直插需要移动位置,所以数据信息量大时不好 (7)若基本有序;采用直插、冒泡;...