选择排序和冒泡排序都是基于元素交换的,因此你的分类错误
冒泡排序基本思想:每次将最重的一个沉入海底
选择排序基本思想:每次扫描最重的一个与第一个交换
并且,选择和冒泡的时间复杂度是一样的(都是O(N^2))
应用交换排序基本思想的主要排序方法有:冒泡排序(Bubble sort)和快速排序(Quick sort)。交换排序
所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。下面是java语言实现一个交换排序的函数:
public class BubbleSort {
public static int[] BubbleSort(int[] array){
for(int i = 0; i < array.length - 1; i++){
for(int j = 0; j < array.length - 1 - i; j++){
// 内部循环的边界要比长度小一
if(array[j] > array[j + 1]){
//相邻的两个元素比较,将大的放到最右边
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
public static void main(String[] args) {
int[] array = { 25, 36, 21, 45, 98, 13};
System.out.println(Arrays.toString(array));
BubbleSort.bubbleSort(array);// 调用快速排序的方法
System.out.println(Arrays.toString(array));// 打印排序后的数组元素
}
也就是两两比较,以数组为例,比较过程:
第一轮:数组下标为0的元素与1的元素相比,25<36,正序,指针后移,36>21反序,交换36和21,指针后移,36<45正序,指针后移,45<98正序,指针后移,98>13反序,交换98和13,最后98位于为底端,也就是数组的末尾。比较次数为(n-1)
第二轮:还是从数组下标为0开始两两比较,在第一比较后的结果98就不参与比较,比较次数为(n-2);
......
5 3 8 9 3 4 array.Length=6
I 0 1 2 3 4 6
J 0 358934
1 358934
2 358934
3 358394
4 358349
353489
334589
334589
I=0时将最大的数放到了最后边;i=1时将倒数第二大的数放到了倒数第二的位置
当然算法是要学习的,这些算法自己都要理解,用的时候呢,就用现成的就好了,如果有特殊需求的排序,当然你可以自己实现比较器
不谢请叫我红领巾
快速排序的基本思想
通过一趟排序将待排记录分割成独立两部分,其中一部分记录的关键字均比另一部分记录的关键小,则可以分别对这两部分记录继续进行排序,以达到这个序列有序。
java实现快速排序
分类:算法2012-02-23 11:49 19506人阅读评论(9) 收藏举报javalistinteger算法数据结构string
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘记了。虽然现在做java上层开发基本上用不到算法,但是还是感觉算法是一种思想,是一种灵魂,所以又不仅翻开了严蔚敏老师的数据结构,一个一个把以前忘记的算法实现一遍。
快速排序的基本思想:
通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分继续进行排序,直到整个序列有序。
先看一下这幅图:
把整个序列看做一个数组,把第零个位置看做中轴,和最后一个比,如果比它小交换,比它大不做任何处理;交换了以后再和小的那端比,比它小不交换,比他大交换。这样循环往复,一趟排序完成,左边就是比中轴小的,右边就是比中轴大的,然后再用分治法,分别对这两个独立的数组进行排序。
[html]view plaincopy
1.public int getMiddle(Integer[] list, int low, int high) {
2. int tmp = list[low]; //数组的第一个作为中轴
3. while (low 4. while (low 5. high--; 6. } 7. list[low] = list[high]; //比中轴小的记录移到低端 8. while (low 9. low++; 10. } 11. list[high] = list[low]; //比中轴大的记录移到高端 12. } 13. list[low] = tmp; //中轴记录到尾 14. return low; //返回中轴的位置 15. } 递归形式的分治排序算法: [html]view plaincopy 1.public void _quickSort(Integer[] list, int low, int high) { 2. if (low 3. int middle = getMiddle(list, low, high); //将list数组进行一分为 二 4. _quickSort(list, low, middle - 1); //对低字表进行递归排序 5. _quickSort(list, middle + 1, high); //对高字表进行递归排序 6. } 7. } [html]view plaincopy 1.public void quick(Integer[] str) { 2. if (str.length > 0) { //查看数组是否为空 3. _quickSort(str, 0, str.length - 1); 4. } 5. } 编写测试方法: [html]view plaincopy 1.public class TestMain { 2. 3. /** 4. * @param args 5. */ 6. public static void main(String[] args) { 7. // TODO Auto-generated method stub 8. Integer[] list={34,3,53,2,23,7,14,10}; 9. QuicSort qs=new QuicSort(); 10. qs.quick(list); 11. for(int i=0;i 12. System.out.print(list[i]+" "); 13. } 14. System.out.println(); 15. } 16. 17.} 看一下打印结果吧: 2 3 7 10 14 23 34 53 这样就排序好了,快速排序是对冒泡排序的一种改进,平均时间复杂度是O(nlogn)。 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上, 1、交换排序 1)气泡排序(bubble sorting) 也是一种简单排序方法,T(n)=O(n2) 算法:A[n],第一次排序区间为A[0]~A[n-1],第二次排序区间为A[1]~A[n-1,]…,最后一次排序区间为A[n-2]~A[n-1],每次排序轻者上浮,即排序区间最小者交换到排序区间的第一个位置,经n-1次排序。完成排序过程。 Example 1 #include void display(ET a[],int n) { for(int i=0;i 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的, 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort,它的参数是一个数组A[1..n],包含了n 个待排序的数。用伪代码表示直接插入排序算法如下: InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是,通过一趟排序将待排序序列分割成独立的两部分,其中一 部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序序列为数组A[1..n],首先选取第一个数A[0],作为枢轴(pivot),然后按照下述原则重新排列其余数:将所有比A[0]大的数都排在它的位置之前,将所有比A[0]小的数都排在它的位置之后,由此以A[0]最后所在的位置i 作为分界线,将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey,则首先从high 所指位置起向前搜索,找到第一个小于pivotkey 的数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 的数,并将其移到高端,重复这两步直至low=high。最后,将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下: Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 冒泡排序的算法及其程序实现 浙江省慈溪中学施迪央 教学分析: 本节课是浙江教育出版社出版的普通高中课程标准实验教科书《算法与程序设计》第二第3节以及第五章第3节的部分教学内容。 一组不长的数据(如5个),从小到大排序,对学生来说是一件容易的事情,但他们并不知道计算机是怎么实现排序的,同时他们也没见识过计算机对大量数据(如1000个)的排序。学习排序有助于学生对计算机工作原理的认识。冒泡排序对学生来说初次接触,但前面的枚举算法和解析算法的部分内容对学习排序有一定的帮助,如数组变量的定义及使用方法、双重循环的使用方法及特点以及如何通过键盘输入一批数据(即text1_keypress()事件)在前面都已涉及,冒泡排序的学习又可以巩固前面的知识。 关于冒泡排序的算法及程序实现我安排了3个课时,本案例是在教室内完成的2节随堂课,第3课时安排学生上机实践:对键盘输入的一批数据进行冒泡排序。 教学目标: 1、知识与技能: 了解排序及冒泡排序的概念及特点 掌握冒泡排序算法的原理 初步掌握冒泡排序的程序实现 2、过程与方法: 理解冒泡排序的分析过程,并初步掌握用冒泡排序算法来设计解决简单的排序问题 3、情感态度与价值观: 通过冒泡排序算法的分析过程,培养学生思维的严谨性以及用科学方法解决问题的能力使学生深入理解计算机的工作原理,激发了学生学习程序兴趣。 教学重点: 冒泡排序算法的原理 教学难点: 分析冒泡排序的实现过程 教学策略: 讲授法与探究法。教师讲授、学生听讲,教师提问、学生动脑,层层深入,步步为营,一切水到渠成。 教学准备: 编写好手动输入一批的数据的冒泡排序的程序 编写好计算机自动生成数据的冒泡排序的程序 课堂中使用的教学课件 教学过程: 一、问题引入 问题一:什么是排序? 所谓排序,把杂乱无章的一列数据变为有序的数据,比如7,3,4,8,1这五个数据从小到大排序,结果是1,3,4,7,8,我们很容易排出来。那么电脑是怎么进行排序的呢?问题二:一批数据在VB中如何存储的?比如如何存储六位裁判为一位运动员评出的分数? 用数组变量来存储一批类型、作用相同的数据,如分别用d(1),d(2),d(3),d(4),d(5),d(6)来存储六位裁判给出的分数。 问题三:如果运动员的最后得分是从这6个分数中去掉最高分与最低分后的平均分,你认为 C选择排序: #include 选择排序和冒泡排序都是基于元素交换的,因此你的分类错误 冒泡排序基本思想:每次将最重的一个沉入海底 选择排序基本思想:每次扫描最重的一个与第一个交换 并且,选择和冒泡的时间复杂度是一样的(都是O(N^2)) 应用交换排序基本思想的主要排序方法有:冒泡排序(Bubble sort)和快速排序(Quick sort)。交换排序 所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。下面是java语言实现一个交换排序的函数: public class BubbleSort { public static int[] BubbleSort(int[] array){ for(int i = 0; i < array.length - 1; i++){ for(int j = 0; j < array.length - 1 - i; j++){ // 内部循环的边界要比长度小一 if(array[j] > array[j + 1]){ //相邻的两个元素比较,将大的放到最右边 int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } return array; } public static void main(String[] args) { int[] array = { 25, 36, 21, 45, 98, 13}; System.out.println(Arrays.toString(array)); BubbleSort.bubbleSort(array);// 调用快速排序的方法 System.out.println(Arrays.toString(array));// 打印排序后的数组元素 } 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院《数据结构》实验报告——排序.docx
交换排序和归并排序
算法排序问题实验报告
冒泡排序的算法及其程序实现
选择排序和冒泡排序的C++和C
冒泡排序 交换排序
实验报告-排序与查找