最新整理书籍,无意间翻出大学时期数据结构课本,随便翻阅了其中关于排序这一章,粗略的看了下突然觉得比较陌生,作为计算机基础的东西,自己工作了反而用的比较少,平时自己也没有太关注,为了以后万一需要找工作方便复习这些东西,今写于此。
快速排序:快速排序是对冒泡排序的一种改进,冒泡排序是比较的相邻两个元素,故比较的次数以及元素移动的频率比较大。快速排序有效的改进了这一不足,比较的元素位置相隔比较远,并且是由两端向中间比较。
下面基于java语言实现快速排序算法。
private static int quickSort(int low, int high , int a[] ) {
int tmp = a[low]; //一般选取数组第一个元素为比较的元素
while (low < high) {
//从数组的右边也就是数组末尾向前开始比较,小的放在数组前段,大的放置于后段
//当后段元素比tmp大,则不需移动直接进行下一个元素比较
while ((low < high) && a[high] > tmp) {
high--;
}
//当遇到后段元素比tmp小直接把后端元素交换至迁low位置
a[low] = a[high];
//tmp交换至后端之后,开始和前段元素进行比较
while (low < high && a[low] < tmp) {
low++;
}
//交换前端元素到后端
a[high] = a[low];
}
//这是第一趟排序完成,tmp此时至于数组个元素大小的最中间
a[low] = tmp;
//返回中间位置即数组中间位置的下标
//到此时整个数组的排序并未完成,完成的只是一趟,后续的排序原理相同,只是比较的数组起始位置下标不同,故可以采用递归算法实现。
return low;
}
private static void quick(int low, int high , int a[] ) {
if (a.length > 0 && low < high){
int middle = quickSort(low, high, a);
quick(low, middle - 1, a);
quick(middle + 1, high, a);
}
插入排序:
public void insertSort1(int a[]) {
int j; // 当前值的位置
int i; // 指向j前的位置
int key; // 当前要进行插入排序的值
// 从数组的第二个位置开始遍历值
for (j = 1; j < a.length; j++) {
key = a[j];
i = j - 1;
// a[i]比当前值大时,a[i]后移一位,空出i的位置,好让下一次循环的值后移
while (i >= 0 && a[i] > key) {
a[i + 1] = a[i]; // 将a[i]值后移
i--; // i前移
}// 跳出循环(找到要插入的中间位置或已遍历到0下标)
a[i + 1] = key; // 将当前值插入
for (int n = 0; n < a.length; n++) {
System.out.print(a[n] + " ");
}
System.out.println("\n");
}
}
分享到:
相关推荐
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡...在研究学习了之前几种排序算法的基础上,讨论发现一种新的排序算法,并通过了进一步的探索,找到了新的排序算法较之前几种算法的优势与不足。
数据结构课程设计(内部排序算法比较_C语言) 数据结构课程设计(内部排序算法比较_C语言)
冒泡排序 快速排序 直接插入排序 简单选择排序 希尔排序 堆排序算法等对正序随机数,逆序随机数,无序随机数进行排序,并统计关键词比较次数 记录移动次数的c++代码
对各种排序算法的一个总结,分析了几种常用算法的思想和实现过程。
3.待排序数据量分别取n=10,30,50,100,1000时,计算每种算法在排序过程中对排序码的比较次数和元素的移动次数以及它们的和,按对选择、冒泡、直接插入、希尔、快速、堆、归并等几种排序算法进行升序排序。
数据结构中几种常见的排序算法之比较,比较常见的冒泡排序、快速排序等
一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 二、数据结构的实现 16 1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4....
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 【基本要求】 (1)实现各种内部排序。包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受
比二分法更快的算法-算法问题:扔杯子的几种方法,排序算法数据结构 最快的排序算法
(1)对以下6种常用的内部排序算法进行比较z起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于1005其中的数据要用伪随机数产生程序产生:至少要用5组不同的输入数据作比较...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 (1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100(原始数据不...
数据结果中,实现排序的方法,有快速排序,希尔排序,直接排序,直接插入排序,气泡排序,选择排序等等!
现在有 1 亿的数据,请选择合适的排序算法与数据结构,在有限的时间内完成进行排序。 选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大...
数据结构报告,包括插入排序(直接插入排序、希尔排序),交换排序(起泡排序、快速排序),选择排序(直接选择排序、堆排序),归并排序、分配排序的基本思想、复杂度分析以及稳定行分析。
大学数据结构实验 涉及的知识点:插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
java编写的几种排序算法,包括冒泡排序、快排、堆排序等,用于学习数据结构,使用Java原生sdk实现,可以运行。
主要用C++实现了数据结构中的排序算法 包括 直接排序 基数排序 堆排序 等! 可以自己看一下。
数据结构课程设计,主要是对内部排序算法比较!
c++的几种常见的大小排序的算法的模板,包括冒泡排序、选择排序、木桶排序、快速排序等,这些不同的算法的复杂度和效率也不同,里面有说明