- 浏览: 2785 次
- 性别:
- 来自: 成都
最新评论
排序简单理解即为将一个数据元素的任意序列,重新排列成一个按关键字有序的序列
常用的排序算法有以下几类:插入排序(直接插入排序,希尔排序),选择排序(简单选择排序,堆排序),交换排序(冒泡排序,快速排序),归并排序,基数排序。排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量,进而影响整个软件的性能。下面对这些算法一一的介绍他们究竟是怎么排的。
1.直接插入排序
思路:逐个考察每个待排序元素,将每一个新元素插入到前面已经排好序的序列中适当的位置上,使得新序列仍然是一个有序序列
2.希尔排序
思路:首先将待排序的元素分为多个子序列,使得每个子序列的元素个数相对较少,对各个子序列分 别进行直接插入排序,待整个待排序序列“基本有序”后,再对所有元素进行一次直接插入排序
注意:希尔排序通过对数组 以一定间隔相隔的位置 进行插入排序,以达到让数据快速出现在它应该出现的位置的周围,使数组逐步接近基本有序。随着间隔的减少,数组越来越接近基本有序,最后间隔为1时,变成标准的插入排序。
数据的间隔有多种算法,一般要求间隔序列之间互质,此处使用Kunth序列:h = h * 3 + 1
3.简单选择排序
思路:每一趟从 (i=1,2,…,n)个元素中选取一个关键字最小的元素作为有序序列中第 i 个元素
4、堆排序
思路:堆排序,顾名思义,就是基于堆
堆分为最大堆和最小堆,其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子,最小堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求,其实很好理解。有了上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。
或者说,堆排序将所有的待排序数据分为两部分,无序区和有序区。无序区也就是前面的最大堆数据,有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加,无序区元素个数减少的过程。当无序区元素个数为1时,堆排序就完成了。
堆分为大顶堆(父节点大于子节点)和小顶堆(父节点小于子节点),根节点是最大的节点(或者最小的节点),每次挑出根节点之后,将剩余的节点进行重新建堆。
5、冒泡排序
思想:交换类排序主要是通过两两比较待排元素的关键字,若发现与排序要求相逆,则“交换”之
6、快速排序
思想:选 出一个关键字,比他小的放到他的左边,大的放到右边,设置两个指针,同时与关键字进行比较。举个例子:期末考试到了,考试完了我们要把成绩排序,我们先选 60为几个分数,大于等于60分的排到一边,小于60分的排到另一边,之后对小于60分的同学和大于60分的同学进行同样的排序。
7、归并排序
思路:就是相邻两个元素组成一个组,组内进行排序,之后再将组内元素增加,循环比较
1.划分:将待排序的序列划分为大小相等(或大致相等)的两个子序列;
2.治理:当子序列的规模大于 1 时,递归排序子序列,如果子序列规模为 1 则成为有序序列;
3.组合:将两个有序的子序列合并为一个有序序列。
8、基数排序
思路:就是先对个位进行比较,进行排序,再对十位进行比较,进行排序……最后对最高位进行比较,进行排序。举个例子:每年在大学里我们都要进行评优,什么样的学生是最优的学生?各方面都要进行比较——成绩、人品、道德等
常用的排序算法有以下几类:插入排序(直接插入排序,希尔排序),选择排序(简单选择排序,堆排序),交换排序(冒泡排序,快速排序),归并排序,基数排序。排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量,进而影响整个软件的性能。下面对这些算法一一的介绍他们究竟是怎么排的。
1.直接插入排序
思路:逐个考察每个待排序元素,将每一个新元素插入到前面已经排好序的序列中适当的位置上,使得新序列仍然是一个有序序列
class InsertSort { public static void main(String[] args) { int[] a = {1,5,3,8,4,3,8}; sort(a); print(a); } private static void sort(int[] a) { int temp; for(int i=1; i<a.length; i++) { int pos = i; //确定位置,在此位置左边的数组是有序的。 temp = a[i]; //根据位置确定要插入的数值。 while(pos>0 && a[pos-1]>temp) { //选择第一个不大于要插入数值的的位置 a[pos] = a[pos - 1]; //将数据以此向后移动 pos--; } a[pos] = temp; //将指定数值插入恰当位置 } } private static void print(int[] a) { for(int i: a) System.out.print(i + " "); System.out.println(); } }
2.希尔排序
思路:首先将待排序的元素分为多个子序列,使得每个子序列的元素个数相对较少,对各个子序列分 别进行直接插入排序,待整个待排序序列“基本有序”后,再对所有元素进行一次直接插入排序
注意:希尔排序通过对数组 以一定间隔相隔的位置 进行插入排序,以达到让数据快速出现在它应该出现的位置的周围,使数组逐步接近基本有序。随着间隔的减少,数组越来越接近基本有序,最后间隔为1时,变成标准的插入排序。
数据的间隔有多种算法,一般要求间隔序列之间互质,此处使用Kunth序列:h = h * 3 + 1
class ShellSort { public static void main(String[] args) { int[] a = {9,8,7,6,5,4,3,2,1}; sort(a); println(a); } private static void println(int[] a) { for(int i: a) System.out.print(i + " "); System.out.println(); } private static void sort(int[] a) { int h = 1; while(h <= a.length/3) h = h * 3 + 1; //产成Kunth序列 while(h > 0) { for(int i = h; i < a.length; i++) { //对每个数据进行间隔为h的插入排序 int pos = i; int temp = a[i]; while(pos >= h && a[pos - h] > temp) { a[pos] = a[pos-h]; pos -= h; } a[pos] = temp; } h = (h - 1) / 3; //减小间隔值 } } }
3.简单选择排序
思路:每一趟从 (i=1,2,…,n)个元素中选取一个关键字最小的元素作为有序序列中第 i 个元素
class Select { public static void main(String[] args) { int[] a = {2,4,6,3,6,2,6,4,9}; sort(a); print(a); } private static void sort(int[] a) { int temp; for(int i=0; i<a.length-1; i++) { int min = i; for(int j=i+1; j<a.length; j++) { if(a[j] < a[min]) min = j; } if(min != i) { temp = a[min]; a[min] = a[i]; a[i] = temp; } } } private static void print(int[] a) { for(int i: a) System.out.print(i + " "); System.out.println(); } }
4、堆排序
思路:堆排序,顾名思义,就是基于堆
堆分为最大堆和最小堆,其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子,最小堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求,其实很好理解。有了上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。
或者说,堆排序将所有的待排序数据分为两部分,无序区和有序区。无序区也就是前面的最大堆数据,有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加,无序区元素个数减少的过程。当无序区元素个数为1时,堆排序就完成了。
堆分为大顶堆(父节点大于子节点)和小顶堆(父节点小于子节点),根节点是最大的节点(或者最小的节点),每次挑出根节点之后,将剩余的节点进行重新建堆。
class Node { //表示装数据的节点 private int key; //排序的关键字 private Object value; //数据 Node(int key, Object value) { this.key = key; this.value = value; } int key() { return key; } Object value() { return value; } } class Heap { private Node[] array; //序排序的数组 private int pos; //当前有效数据的个数 Heap(Node[] array) { this.array = array; //装入要排序的数组 pos = array.length; } private Node remove() { //删除堆的顶 Node result = array[0]; array[0] = array[--pos]; //将最后一个元素提至堆定 trickleDown(0); //将堆顶下降为恰当位置 return result; } private void trickleDown(int index) { Node top = array[index]; //存放要下降的数据 int left = getLeft(index); //得到左子的位置 int right = getRight(index); //得到右子的位置 int current; //当前可能要下降的位置 if(left < pos && right < pos) //左右子节点有效,当前的位置设置为左右子节点中小的那个 current = array[left].key() > array[right].key() ? left : right; else if (left < pos) current = left; //如果左子节点有效,则当前位置设置为左子节点 else current = -1; //没有可以下降的位置 while(current != -1 && array[current].key() > top.key()) {//当前节点有效且大于要下降的数据 array[index] = array[current]; //将当前节点向上提升。 index = current; //重复以上过程 left = getLeft(index); right = getRight(index); if(left < pos && right < pos) current = array[left].key() > array[right].key() ? left : right; else if (left < pos) current = left; else current = -1; } array[index] = top; //将暂存的数据放入恰当的位置 } private int getParent(int index) { return (index-1)/2; } private int getLeft(int index) { return 2 * index + 1; } private int getRight(int index) { return 2 * index + 2; } public void sort() { for(int i=array.length/2 -1; i>=0; i--) { trickleDown(i); } for(int i=array.length-1; i>=0;i--) array[i] = remove(); } public static void main(String[] args) { Node[] nodes = {new Node(50,"hello"), new Node(20,"jason"), new Node(60,"peter"), new Node(50,"orange"), new Node(30,"temp"), new Node(40,"hello"), new Node(90,"nasen"), new Node(25,"kaka")}; Heap heap = new Heap(nodes); heap.sort(); print(nodes); } private static void print(Node[] nodes) { for(Node node: nodes) System.out.println(node.key() + "-----" + node.value()); } }
5、冒泡排序
思想:交换类排序主要是通过两两比较待排元素的关键字,若发现与排序要求相逆,则“交换”之
class Bubble { public static void main(String[] args) { int[] a = {6,3,2,6,3,2,9,7}; sort(a); print(a); } private static void print(int [] a) { for(int i: a) System.out.print(i + " "); System.out.println(); } private static void sort(int[] a) { int temp; for(int i=a.length-1; i>0; i--) { for(int j=0; j<i; j++) { if(a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } }
6、快速排序
思想:选 出一个关键字,比他小的放到他的左边,大的放到右边,设置两个指针,同时与关键字进行比较。举个例子:期末考试到了,考试完了我们要把成绩排序,我们先选 60为几个分数,大于等于60分的排到一边,小于60分的排到另一边,之后对小于60分的同学和大于60分的同学进行同样的排序。
class Quick { public static void main(String[] args) { int[] a = {6,9,5,4,2,45,23,45,53,3,7}; int pos = getPartitionPos(a,0,a.length); sort(a,0,a.length); println(a); } public static void println(int[] a) { for(int i: a) System.out.print(i + " "); System.out.println(); } public static void sort(int[] a,int begin, int end) { if(begin >= end) return; int pos = getPartitionPos(a,begin,end); sort(a,begin,pos); sort(a,pos + 1, end); } private static int getPartitionPos(int[] a, int begin, int end) { int pos = begin; int value = a[begin]; while(true) { while(begin < end && a[--end] > value); //从结尾向左找到第一个比枢纽小的数值 while(begin < end && a[++begin] < value); //从结尾向右找到第一个比枢纽大的数值 if(begin < end) { //如果需交互 a[pos] = a[end]; //将比枢纽小的值放在空位 a[end] = a[begin]; //将比枢纽大的值放在原来从右向左第一个比枢纽小的值的位置上 pos = begin; //将从左向右第一个比枢纽大的值的位置标志为空位 } else break; } if(pos != begin) { //如果空位与结束位置不等 a[pos] = a[begin]; //将空位置为结束时位置的值 a[begin] = value; //将结束位置放置枢纽 } else a[pos] = value; return begin; } }
7、归并排序
思路:就是相邻两个元素组成一个组,组内进行排序,之后再将组内元素增加,循环比较
1.划分:将待排序的序列划分为大小相等(或大致相等)的两个子序列;
2.治理:当子序列的规模大于 1 时,递归排序子序列,如果子序列规模为 1 则成为有序序列;
3.组合:将两个有序的子序列合并为一个有序序列。
class Merge { public static void main(String[] args) { int[] a = {3,2,5,2,0,6,3,7}; sort(a,0,a.length); print(a); } public static void sort(int[] a, int p1, int p3) { if((p3-p1) <= 1) return; //判断是否不需要继续递归 int p2 = (p3 + p1)/2; //计算中间位置p2 sort(a,p1,p2); //将p1 ~ p2之间递归排序 sort(a,p2,p3); //将p2 ~ p3之间递归排序 merge(a,p1,p2,p3); //合并p1~p2,p2~p3 } public static void merge(int[] a, int p1, int p2 ,int p3) { int[] c = new int[p3 - p1]; int n = p1, m = p2, i = 0; while(n< p2 && m<p3) { if(a[n] < a[m]) c[i++] = a[n++]; else c[i++] = a[m++]; } while(n < p2) c[i++] = a[n++]; while(m < p3) c[i++] = a[m++]; for(int j=0; j<c.length; j++) a[p1 + j] = c[j]; } public static void print(int[] c) { for(int i: c) System.out.print(i + " " ); System.out.println(); } }
8、基数排序
思路:就是先对个位进行比较,进行排序,再对十位进行比较,进行排序……最后对最高位进行比较,进行排序。举个例子:每年在大学里我们都要进行评优,什么样的学生是最优的学生?各方面都要进行比较——成绩、人品、道德等
class Queue { int[] values; int head = -1; int tail = -1; Queue(int size) { values = new int[size]; } boolean isEmpty() { return head == tail; } void put(int value) { values[++head] = value; }; int get() { return values[++tail]; }; void clean() { head = -1; tail = -1; } } class Radix { public static void main(String[] args) { int[] a = {6,4,3,2,4,1,2}; sort(a,4); println(a); } /** * @param radix 2的幂 * @param a 源数据数组 */ public static void sort(int[] a,int radix) { int base = 1<<radix; Queue[] q = new Queue[base]; for(int i=0; i<base; i++) { q[i] = new Queue(a.length); } int bit = 0; int sum; do { sum = 0; //判断是否要再继续 for(int i: a) { int remain = i >> bit; q[remain&(base - 1)].put(i); sum |= remain; } bit += radix; //从队列中取出数据,放入原数组中 int i = 0; for(int j=0; j<q.length; j++) { while(!q[j].isEmpty()) a[i++] = q[j].get(); q[j].clean(); } } while(sum > 0); } public static void println(int[] a) { for(int i: a) System.out.print(i + " "); System.out.println(); } }
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
常用排序算法的动态演示系统的开发,演示冒泡排序法、快速排序法、直接插入排序法、折半插入排序法、树形选择排序法
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
总结了各种排序算法,并用C++代码实现,并有演示
桶式排序法桶式排序法桶式排序法桶式排序法
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数...