- 浏览: 400918 次
- 性别:
- 来自: 天津
文章分类
最新评论
-
junchao_qin:
[img][flash=200,200][url][img]引 ...
MyEclipse中使用VSS插件 -
tigerwood008:
IE11不好用!!
js弹出窗口 + 获取上传文件全路径 -
TheMatrix:
$.ajaxSetup({async : false});这种 ...
jquery 中的post和get方法如何同步 -
多多成长记:
Blazeds与java通信 -
ZED.CWT:
[align=ceiinter][/align]
java中利用JFrame创建窗体 【转】
参考:http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.2.htm
http://www.stuhack.com/biancheng/c/39543.html
http://blog.csdn.net/agwujiang/article/details/5829443
冒泡排序:
package cn.edu.tju.sortArithmetic; /*冒泡排序跟选择排序,貌似没啥区别啊 * 时间复杂度:最差、平均O(n^2),最好O(n),空间复杂度1 * 稳定排序 */ public class BubbleSort { public static void bubble(int[] arr){ for(int i = arr.length - 1; i > 0; i --){ for(int j = 0; j < i; j ++){ if(arr[i] < arr[j]){ Util.swap(arr, i, j); } } } } }
选择排序:
package cn.edu.tju.sortArithmetic; /* * 基本思想:首先在未排序的序列中找到最小元素,放到序列起始位置。 * 然后从剩下的未排序的元素中继续寻找最小元素,放到已排好的序列末尾 * * 选择排序跟冒泡排序,貌似没啥区别啊 * 时间复杂度:最差、平均O(n^2),空间复杂度1 * 不稳定排序 */ public class SelectionSort { public static void selection(int[] arr){ for(int i = 0; i < arr.length; i ++){ for(int j = i + 1; j < arr.length; j ++){ if(arr[i] > arr[j]){ Util.swap(arr, i, j); } } } } }
插入排序:
package cn.edu.tju.sortArithmetic; /* * 插入排序基本思想: * 1从第一个元素开始,该元素默认已被排序 * 2取出下一个元素,在已经排序的元素序列中从后向前扫描 * 3若新元素小于原元素(已排序),则将原元素后移 * 重复3,直到找到新元素大于或等于原元素的位置,将新元素插入 * 重复2 * * 时间复杂度:最差、平均都是O(n^2),最好O(n),空间复杂度1 * 稳定排序 */ public class InsertionSort { public static void insertion(int[] arr){ for(int i = 0; i < arr.length; i ++){ for(int j = i; j > 0; j --){ if(arr[j] < arr[j - 1]){ Util.swap(arr, j, j - 1); Util.output(arr); } } } } }
希尔排序:动画演示
package cn.edu.tju.sortArithmetic; /* * 希尔排序基本思想: * /2取增量d,将i = i + d的元素作为一组,分成几组之后,在各组内进行插入排序,直到d = 1时,也即每个元素一组时,完成排序 * 如若有10个元素,则增量取为5,2,1,增量的取法不定 * 第一次排序d=5; 分组:0,5;1,6;2,7;3,8;4,9 第一组作为已排好序的初始序列,然后后面各组分别通过插入排序插入 * 第二组d=2;分组:0,2,4,6,8;1,3,5,7,9; * 第三组d=1;分组:0,1,2,3,4,5,6,7,8,9; * * 希尔排序性能优于直接插入排序 * 时间复杂度:O(nlogn),空间复杂度:1 * 不稳定排序 */ public class ShellSort { public static void shell(int[] arr){ int increment = arr.length; while((increment /= 2) > 0){ for(int i = increment; i < arr.length; i ++){ for(int j = i; j - increment >= 0; j -= increment){ if(arr[j] < arr[j - increment]){ Util.swap(arr, j, j - increment); } } } } } }
快速排序:
package cn.edu.tju.sortArithmetic; /* * 快速排序基本思想: * 1设置关键值X,一般为数组的第一个值,设定指针开始i=0,结束j=length-1 * 2数组从后往前扫描,找到第一个小于X的元素,并与X交换 * 3数组从前往后扫描,找到第一个大于X的元素,并与X交换 * 4重复2,3步,直到i >= j结束一次快速排序,此时所有大于X的数全部在X之后,小于X的数全部在X之前 * 递归此过程,对X之前的序列和X之后的序列分别进行快速排序,从而完成全部数据的快速排列 * * 时间复杂度:平均O(nlogn),最坏O(n^2),空间复杂度O(logn) * 不稳定排序 */ public class QuickSort { public static void quick(int[] arr, int left, int right) { if (left >= right) { return; } int pivotpos = partion(arr, left, right); quick(arr, left, pivotpos - 1); quick(arr, pivotpos + 1, right); } public static int partion(int[] arr, int i, int j) { int pivotpos = i;//表示关键值位置 while (i < j) { //2数组从后往前扫描,找到第一个小于X的元素,并与X交换 while (i < j && arr[j] > arr[pivotpos]) { j--; } Util.swap(arr, pivotpos, j); pivotpos = j; //3数组从前往后扫描,找到第一个大于X的元素,并与X交换 while (i < j && arr[i] < arr[pivotpos]) { i++; } Util.swap(arr, pivotpos, i); pivotpos = i; } return pivotpos; } }
归并排序:貌似有些问题。。。待解决
package cn.edu.tju.sortArithmetic; /* * 归并排序的算法思想:把待排序序列分成相同大小的两个部分,依次对这两部分进行归并排序, * 完毕之后再按照顺序进行合并。 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 * 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个 * 有序表,称为2-路归并。 * * 工作原理: * 1将序列每相邻的两个数字进行归并操作merge,形成floor(n/2)个序列,排序后每个序列包含两个元素 * 2将上述序列再次归并,形成floor(n/4)个序列,每个序列包含4个元素 * 3重复2,直到所有元素排序完毕 * * 时间复杂度:最差、平均和最好都是O(nlogn),空间复杂度O(n) * 稳定排序 */ public class MergeSort { public static void mergeSort(int[] arr, int left, int right){ if(left < right){ int mid = (left + right)/2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, mid + 1, right); } } public static void merge(int[] arr, int start1, int end1, int start2, int end2){ int i = start1;//前半段指针 int j = start2;//后半段指针 int k = 0;//整个序列的指针 int[] temp = new int[end2 - start1 + 1];//建立临时数组,长度为两段序列的长度之和 while(i <= end1 && j <= end2){//依次从两个子序列中取出元素较小的放入temp System.out.println(i + ", " + j); if(arr[i] < arr[j]){ temp[k++] = arr[i++];//等价于temp[k] = arr[i]; k ++; i ++; }else{ temp[k++] = arr[j++]; } } //把剩下的元素一次放入temp,肯定只剩下一方 while(i <= end1){ temp[k++] = arr[i++]; } while(j <= end2){ temp[k++] = arr[j++]; } //System.out.println(tem) for(int m = start1; m < temp.length; m ++){ arr[m] = temp[m]; } } }
归并排序:貌似有些问题。。。待解决
package cn.edu.tju.sortArithmetic; /* * 归并排序的算法思想:把待排序序列分成相同大小的两个部分,依次对这两部分进行归并排序, * 完毕之后再按照顺序进行合并。 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 * 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个 * 有序表,称为2-路归并。 * * 工作原理: * 1将序列每相邻的两个数字进行归并操作merge,形成floor(n/2)个序列,排序后每个序列包含两个元素 * 2将上述序列再次归并,形成floor(n/4)个序列,每个序列包含4个元素 * 3重复2,直到所有元素排序完毕 * * 时间复杂度:最差、平均和最好都是O(nlogn),空间复杂度O(n) * 稳定排序 */ public class MergeSort { public static void mergeSort(int[] arr, int left, int right){ if(left < right){ int mid = (left + right)/2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, mid + 1, right); } } public static void merge(int[] arr, int start1, int end1, int start2, int end2){ int i = start1;//前半段指针 int j = start2;//后半段指针 int k = 0;//整个序列的指针 int[] temp = new int[end2 - start1 + 1];//建立临时数组,长度为两段序列的长度之和 while(i <= end1 && j <= end2){//依次从两个子序列中取出元素较小的放入temp System.out.println(i + ", " + j); if(arr[i] < arr[j]){ temp[k++] = arr[i++];//等价于temp[k] = arr[i]; k ++; i ++; }else{ temp[k++] = arr[j++]; } } //把剩下的元素一次放入temp,肯定只剩下一方 while(i <= end1){ temp[k++] = arr[i++]; } while(j <= end2){ temp[k++] = arr[j++]; } //System.out.println(tem) for(int m = start1; m < temp.length; m ++){ arr[m] = temp[m]; } } }
工具类:包括交换两个元素以及输出。
package cn.edu.tju.sortArithmetic; public class Util { public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void output(int[] arr){ for(int i = 0; i < arr.length; i ++){ System.out.print(arr[i] + " "); } System.out.println(); } }
测试类:
package cn.edu.tju.sortArithmetic; public class Test { public static void main(String[] args){ int[] arr = {5, 7, 9, 3, 4, 1, 2, 6, 8, 0}; //int[] arr = {49, 38, 65, 97, 76, 13, 27}; //BubbleSort.bubble(arr); //SelectionSort.selection(arr); //InsertionSort.insertion(arr); //ShellSort.shell(arr); //QuickSort.quick(arr, 0, arr.length - 1); MergeSort.mergeSort(arr, 0, arr.length - 1); Util.output(arr); } }
- C__排序.rar (2.2 KB)
- 下载次数: 0
发表评论
-
判断二叉树是否平衡及计算二叉树深度和结点个数
2012-09-01 10:12 7655参考:http://blog.csdn.net/zz19880 ... -
【转】java实现二叉查找树
2012-08-31 09:44 1433转自:http://blog.csdn.net/zyj817 ... -
二叉树及其遍历
2012-08-21 09:50 1512转自:http://www.iteye.com/t ... -
java栈中缀表达式转为后缀表达式
2012-07-19 11:33 2415思路: 遇到数字,则输出。 遇到操作符,入栈,在入栈前若该 ... -
java栈实现括号匹配
2012-07-19 09:48 4507算法思想: 做一个空栈,读入字符。 若字符是左运算符,则入 ... -
【转】java静态变量和实例变量的区别
2012-06-20 11:02 1296转自:http://www.2cto.com/kf/20100 ... -
【转】java中会存在内存泄漏吗,请简单描述。
2012-06-20 10:24 1347java中 ... -
【转】java匿名内部类2
2012-06-12 13:45 1173匿名内部类就是没有名字的内部类。什么情况下需要使用匿名内部类? ... -
【转】java匿名内部类
2012-06-12 13:32 1386java匿名内部类 (2010-11 ... -
【转】JAVA中获取路径
2012-03-25 16:57 818转自:http://wenku.baidu.com/view/ ... -
【转】Map遍历
2012-03-25 16:56 909转自:http://wenku.baidu.com/view/ ... -
【转】java解析xml文件四种方式
2012-03-25 16:54 1327转自:http://wenku.baidu.com ... -
【转】JDOM解析处理xml
2012-03-25 16:52 1196转自http://qingbyqing.iteye.com/b ... -
【转】解析Html页面:HTML Parser的试用
2012-03-24 15:10 1366转自:http://blog.csdn.net/scud/ar ... -
【转】java随机排列数组
2012-02-20 18:58 2329转自:http://blog.csdn.net/liang ... -
设计模式——代理模式
2012-01-06 13:14 1233代理模式: 为其他对象提供一种代理以控制对这个对象的访问 ... -
设计模式——装饰模式
2012-01-05 15:58 1232首先介绍三个重要原则: 依赖倒转原则:高层模块不应该依赖于 ... -
设计模式——策略模式 & 单例模式
2011-12-29 16:26 1476策略模式: * 策略模式定义了算法家族,分别封装起来,让他 ... -
设计模式——简单工厂 VS 工厂方法
2011-12-28 15:07 1144简单工厂模式: 它最大优点在于工厂类中包含了必要的逻辑 ... -
String
2011-12-27 10:53 12291. String s = new String(" ...
相关推荐
最快的排序算法 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),基数...