复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅。
排序
1、概念:
有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}。通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键字满足如下的非递减(非递增)关系,即:Kp1<=Kp2<=Kpn,这样就得到一个按关键字有序的记录序列:{Rp1,Rp2,.......,Rpn}。
2、分类
根据排序时数据所占用存储器的不同,可将排序分为两类。
内部排序:整个排序过程完全在内存中进行,如下:
插入类排序(直接插入排序、折半插入排序、希尔排序);
交换类排序(冒泡排序、快速排序);
选择类排序(简单选择排序、树型选择排序、堆排序);
归并排序;
分配类排序(多关键字排序、链式基数排序、基数排序的顺序表实现));
外部排序:由于待排序记录数据量太大,内存无法容纳全部数据,排序需要借助外部存储设备才能完成(磁盘排序,磁带排序)。
3、稳定性
假设在待排序的序列中存在多个具有相同关键字的记录。设Ki=Kj(1<=i<=n,1<=j<=n,i != j),若在排序前的序列中Ri领先与Rj(即i<=j),经过排序后得到的序列中Ri仍然领先与Rj,则称所用的排序方法是稳定的;反之,当相同关键字的领先关系在排序过程中发生变化,则所用的排序方法是不稳定的。
插入排序:
思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
直接插入排序:
算法思想:假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。
用java实现的代码如下:
package exp_sort;
public class DirectInsertSort {
public static void DircstSort(int array[]) {
int j;
// 循环从第二个数开始,第一个数用做存放待插入的记录
for (int i = 1; i < array.length; i++) {
int temp = array[i];
// 寻找插入位置
for (j = i; j > 0 && temp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
// 将待插入记录插入到已经排序的序列中
array[j] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
DircstSort(array);
}
}
算法分析:最好的情况是待排序记录本身已经按照关键字有序排列,最坏的情况是待排序记录是按照关键字逆序排列的;
时间复杂度是O(N^2),空间复杂度是O(1);该算法是
稳定的排序算法:比较适用于
待排序记录数目较少且基本有序的情况。
折半插入排序:
算法思想:对于有序表进行折半查找,其性能优于顺序查找。
算法实现代码如下:
package exp_sort;
public class BinaryInsertSort {
public static void sort(int array[]) {
int temp, low, mid, high;
for (int i = 1; i < array.length; i++) {
temp = array[i];
low = 0;
high = i -1;
//确定插入位置
while (low <= high) {
mid = (low + high) / 2;
if (temp < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
//记录依次向后移动
for (int j = i; j >= low + 1; j--) {
array[j] = array[j-1];
}
//插入记录
array[low] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
sort(array);
}
}
算法分析:是一种
稳定的排序算法,比直接插入算法明显减少了关键字之间比较的次数,因此
速度比直接插入排序算法快,但记录移动的次数没有变,所以折半插入排序算法的时间复杂度仍然为O(n^2),与直接插入排序算法相同。附加空间O(1)。
分享到:
相关推荐
数据结构中个各种排序法,快速,直接插入,冒泡...
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
主要知识点 插入排序 直接插入排序 O(n2) 希尔排序 O(n(lbn)2) 选择排序 直接选择排序O(n2) 堆排序O(nlbn) 交换排序 冒泡排序O(n2) 快速排序O(nlbn) 二路归并排序O(nlbn) 基数排序O(mn)
主要介绍了javascript数据结构之双链表插入排序实现方法,较为详细的分析了插入排序的原理及双链表插入排序的实现技巧,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下
主要介绍了java数据结构与算法之插入排序,结合实例形式分析了java插入排序的概念、分类、原理、实现方法与相关注意事项,需要的朋友可以参考下
1.1 数据结构的基本概念和术语 1.1.1 引言 1.1.2 数据结构有关概念及术语 1.1.3 数据结构和抽象数据类型(ADT) 1.2 算法描述与分析 1.2.1 什么是算法 1.2.2 算法描述工具——C语言 1.2.3 算法分析技术初步...
1.1 针对考研数据结构的代码书写规范以及C 与C 语言基础1 1.1.1 考研综合应用题中算法设计部分的代码书写规范1 1.1.2 考研中的C 与C 语言基础3 1.2 算法的时间复杂度与空间复杂度分析基础 12 1.2.1 考研中的算法时间...
数据结构十大排序详解,插入,希尔,冒泡,快速,选择,堆,归并,桶,基数,二分十个排序的应用
本文实例讲述了JS中的算法与数据结构之常见排序(Sort)算法。分享给大家供大家参考,具体如下: 排序算法(Sort) 引言 我们平时对计算机中存储的数据执行的两种最常见的操作就是排序和查找,对于计算机的排序和...
堆排序作是基本排序方法的一种,类似于合并排序而不像插入排序,它的运行时间为O(nlogn),像插入排序而不像合并排序,它是一种原地排序算法,除了输入数组以外只占用常数个元素空间。 堆(定义):(二叉)堆数据...
下标从 1 开始,B[k]=1+2+3+…+n-1=n(n-1)/2, 所以选 D 4.D 【详解】本题考查各种排序的算法思想,堆排序、冒泡排序、选择排序第一次元素即在相应 的位置上,只有插入排序有可能如问题所述,所以选D。 5.C 【详解】...
在对待排序链表扫描一遍之后,左边子链表的节点值都小于基准的值,右边子链表的值都大于基准的值,然后把基准插入到链表中,并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序,以提高性能。...
树的各种问题(平衡二叉树,调整最小不平衡子树,最小生成树,树的遍历等等)+栈+图的遍历+AOV和AOE网+判定循环队列的满与空+外部排序+内部排序的各种算法讲解及总结+广义表+链表的插入和删除+前后缀表达式的计算+...
二叉查找树(Binary Search Tree,也叫二叉排序树,即Binary Sort Tree)能够支持多种动态集合操作,它可以用来表示有序集合、建立索引等,因而在实际应用中,二叉排序树是一种非常重要的数据结构。 从算法复杂度...
许多排序算法,如冒泡排序、插入排序、归并排序等,都可以用于按字典序对字符串进行排序。此外,字典序也常用于数据结构的遍历,如树的遍历算法中经常采用先序遍历(前序遍历)、中序遍历和后序遍历,这些遍历方式都...
* 数据结构中的所有排序算法(冒泡排序,堆排序,直接插入排序,二路归并排序,快速排序,基数排序,直接选择排序,希尔排序)的例子; * 丰富的数组,位,指针,枚举,结构体,联合体等操作的例子; * 一个...
C语言中数组的排序算法详解——选择法、冒泡法、交换法、插入法、折半法 的C语言代码实现以及相应注释。可以参考本人另一篇博客关于C语言中数组的排序算法详解。
这样的业务场景所需要的数据结构该如何设计呢?拍卖行商品列表是线性的,最容易表达线性结构的是数组和链表。假如用有序数组,虽然查找的时候可以使用二分法(时间复杂度O(logN)),但是插入的时间复杂度是O(N),...