最新整理书籍,无意间翻出大学时期数据结构课本,随便翻阅了其中关于排序这一章,粗略的看了下突然觉得比较陌生,作为计算机基础的东西,自己工作了反而用的比较少,平时自己也没有太关注,为了以后万一需要找工作方便复习这些东西,今写于此。
快速排序:快速排序是对冒泡排序的一种改进,冒泡排序是比较的相邻两个元素,故比较的次数以及元素移动的频率比较大。快速排序有效的改进了这一不足,比较的元素位置相隔比较远,并且是由两端向中间比较。
下面基于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语言实现的几种常见排序算法,包括它们的基本原理、实现细节和性能特点。 首先,让我们从最经典的排序算法——冒泡排序(Bubble Sort)开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步...
根据给定文件的信息,本文将对六种不同...为了直观地展示这些排序算法的性能差异,可以通过绘制条形图的方式来进行对比,比如使用星号表示每种排序算法所需的时间复杂度,从而帮助我们更好地理解它们的特点及应用场景。
本篇文章将深入探讨几种常见的排序算法,并通过Java代码示例进行解析。 ### 1. 插入排序 - **直接插入排序**:在已排序部分后依次插入新元素,不断调整已排序部分,直至整个数组有序。 - **折半插入排序**:改进了...
6. **堆排序**:利用堆这种数据结构所设计的一种排序算法,可以分为大顶堆和小顶堆,适用于大数据量的排序。 7. **二路归并排序**:同样采用分治策略,将待排序序列分成若干个子序列,分别进行排序,再将这些子序列...
### 数据结构经典排序算法之比较 #### 排序的基本概念及其重要性 排序算法作为计算机科学中的基础且关键的一部分,在日常的数据处理工作中扮演着至关重要的角色。通过将数据按照一定的规则进行排列,不仅可以提高...
以上介绍的几种排序算法各有优缺点,适用于不同的场景。例如,插入排序适合于小型数据集或接近有序的数据;快速排序因其较高的平均效率而被广泛应用于实际应用中;归并排序虽然需要较多的额外空间,但其稳定性和较好...
广东工业大学的数据结构实验报告重点关注了几种常见的内部排序算法,包括直接插入排序、选择排序和快速排序。这些算法在不同的场景下具有不同的性能特征。 **直接插入排序**是一种简单直观的排序方法,适用于小规模...
以下是几种常见的排序算法的详细说明: 1. 直接插入排序(Insertion Sort): 直接插入排序是一种简单的排序算法,它通过比较当前元素与前面已排序的元素,将元素逐步插入到正确的位置。在每一轮中,它将一个未排序...
在计算机科学领域中,排序算法是一种基本的算法,它可以将数据按照一定的顺序排列,以便更好地存储、检索和处理数据。排序算法的速度和效率对程序的性能有着至关重要的影响。 1.冒泡排序算法 冒泡排序算法是一种...
数据结构中的排序算法是计算机科学中的重要概念,用于组织和整理数据,以便高效地查找、检索和处理。这里我们将详细讨论几种经典的排序算法,包括快速排序、归并排序、堆排序、Shell排序、插入排序、冒泡排序以及...
冒泡排序 快速排序 直接插入排序 简单选择排序 希尔排序 堆排序算法等对正序随机数,逆序随机数,无序随机数进行排序,并统计关键词比较次数 记录移动次数的c++代码
数据结构中的排序算法是计算机科学中的核心概念,用于组织和管理数据,以便高效地访问和操作。排序将无序的数据序列转换为有序序列,这对于数据分析、数据库查询优化、算法效率提升等多个领域至关重要。以下是几种...
在实现测试程序时,我们可以为每种排序算法设计一个函数,记录每一步的比较和移动操作,最后统计总次数。例如,可以创建一个通用的接口,定义比较和移动的计数器,然后让每个排序算法函数调用这个接口。这样可以保证...
通过对以上几种排序算法的分析,我们可以看出不同算法有着各自的特点和适用场景。例如,在数据规模较小或者对稳定性有一定要求的情况下,插入排序和选择排序是不错的选择;而对于大规模数据的排序任务,则更适合采用...
通过对以上几种排序算法的应用,我们可以观察到不同的排序效果。直接插入排序虽然简单,但在大数据量下效率较低;而希尔排序通过引入增量的概念,大大提高了排序速度。快速排序通过分治法将问题分解为更小的子问题,...
### 数据结构中几种排序算法分析比较 #### 插入排序 **插入排序**是一类简单直观的基于比较的排序算法。其基本思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 #####...
3.待排序数据量分别取n=10,30,50,100,1000时,计算每种算法在排序过程中对排序码的比较次数和元素的移动次数以及它们的和,按对选择、冒泡、直接插入、希尔、快速、堆、归并等几种排序算法进行升序排序。
在计算机科学领域,排序算法是数据结构与算法中不可或缺的一部分,它们用于将一组数据按照特定顺序进行排列。这里我们将深入探讨几种最常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 ...
数据结构中几种常见的排序算法之比较,比较常见的冒泡排序、快速排序等
在数据结构的学习中,排序算法是一项至关重要的内容。实验报告“数据结构实验报告(排序算法)”涵盖了多种经典的排序算法,旨在通过实际编程加深学生对这些算法的理解和应用能力。以下将详细介绍这些排序算法及其...