在学习数据结构的时候,针对数组,有几种典型的排序算法,分别为冒泡排序、插入排序、选择排序和希尔排序,这几种排序算法也是比较常见的。下面是对这些排序算法的一些理解。
要很好的理解排序算法,我觉得最重要是掌握程序执行的流程,并且一个个地试数。试过几次数后,用到的排序算法也就难理解了。
冒泡排序
冒泡排序算法应该说是排序算法中最简单的。但能一次性的写对冒泡排序也是不容易的。冒泡排序最核心的策略就是每次找出最大值(或者最小值)并把其放入到数组的最末端(或者最前端),要排序的元素每次减少1个,以此不断执行,最后就会得到想要的结果。下面是其具体的代码实现:
/**
* 冒泡排序策略:搜索整个数组,比较相邻元素,如果两者的相对大小次序不对,则交换它们,其结果是最大值
* “像水泡一样”移动到数组的最后一个位置上,这也是它在完成排序的数组中合适的位置;然后再次搜索数组,
* 将第二大的值移动到倒数第二个位置上,重复该过程,直至将所有元素移动到正确的位置上
*/
static void sortBubb(int [] arr){
//数组中有length个数,只需要排length-1次
for(int i=0;i<arr.length-1;i++){
//每经过一次排序,就将本次排序中最大的元素放到排序数组的最后一位
//每经过一次排序,要排序的数组元素的个数就减1
for(int j=0;j<arr.length-i-1;j++){
//比较相邻元素的大小,如果后一个元素小于前一个元素,就交换这两个元素,否则什么事也不做
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
插入排序
插入排序的核心思想就是将要插入的元素和已排好序的元素进行比较,并将新元素插入到数组的适当位置。可以分为两步:先比较,再插入。下面是代码实现。
/**
* 插入排序策略:首先按大小秩序排序数组中的前两个值,然后在相对于前两个值的适当位置插入数组的第三个值
* 再在相对于数组前三个值得适当位置插入数组的第四个值,以此类推。每进行以此插入操作,有序子集中的数值个
* 数将递增1.重复此过程,直到数组中的所有值都按照秩序排列为止
*/
static void sortInsert(int arr[]){
//先将arr[0]和arr[1]比较,每次比较的元素个数加1
for(int i=1;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
选择排序
选择排序的核心思想就是先找值,再替换。也就是说,先在数组中找出最大值(或者最小值),然后再将它与数组的最大下标(或最小下标)处的值替换。具体代码如下:
/**
* 选择排序策略:搜索整个数组,找到最小值。将该值与数组中的第一个位置上的值进行交换
* 搜索剩下的数组元素(第一个除外),找到其中的最小值,然后将其与数组中第二个位置上的
* 值进行交换。对数组中的每个位置重复该过程。在该算法结束时,就完成了对数组的排序。
*/
static void sortSelect(int[] arr){
for(int i=0;i<arr.length;i++){
int lowerIndex = i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[lowerIndex]){
lowerIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[lowerIndex];
arr[lowerIndex] = temp;
}
}
希尔排序
希尔排序的效率是比较高的,它的核心思想就是将数组不断分为更小的几个序列,在序列内先进行排序,排好之后再进行一次插入排序。它的实现具体如下:
/**
* 希尔排序策略:希尔排序又称为”缩小增量排序“,先将整个待排序的元素序列分割成若干个子序列(由相隔某
* 个”增量“的元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(
* 增量足够小)时,再对全部元素进行依次直接插入排序
*/
static void sortShell(int[] arr){
//不断缩小增量
for(int increment = arr.length/2;increment>0;increment/=2){
//从一半的位置开始比较
for(int i=increment;i<arr.length;i++){
int temp = arr[i];
int j = 0;
for(j=i;j>=increment;j-=increment){
if(temp < arr[j-increment]){
arr[j] = arr[j-increment];
}else{
break;
}
}
arr[j] = temp;
}
}
}
分享到:
相关推荐
这个压缩包文件“排序算法分析内含程序和论文”显然是一个研究项目,可能包含了作者在研究生阶段对排序算法的深入探讨,以及通过软件绘制的性能比较图表。下面将对排序算法及其相关知识进行详细解析。 首先,排序...
根据提供的信息,我们可以总结出以下关于八种基本排序算法中的两种——冒泡排序(Bubble Sort)与插入排序(Insert Sort)的知识点。 ### 冒泡排序(Bubble Sort) #### 定义 冒泡排序是一种简单的排序算法。它...
选择排序是一种简单的排序算法,其基本思想是每次从未排序的元素中找出最小(或最大)的元素,将其放置到已排序序列的末尾。时间复杂度为O(n^2),虽然简单易懂,但在处理大数据量时效率较低。 **2. 冒泡排序(Bubble...
算法分析与设计排序算法比较 通过对各种排序算法的思想、算法的分析,探究它的使用范围以及时间复杂度和空间复杂度。 冒泡排序算法 冒泡排序算法思想简单描述:在要排序的一组数中,对当前还未排好序的范围内的...
- 空间复杂度方面,大多数排序算法的空间复杂度较低,但归并排序需要额外的存储空间,空间复杂度为O(n)。 - 稳定性方面,归并排序、直接插入排序和冒泡排序是稳定的,而快速排序和堆排序是不稳定的。 在实际应用中...
当然,为了学习和理解,我们也可以自己编写这些基本排序算法的C++代码。 例如,快速排序的C++实现可能如下: ```cpp void quickSort(int arr[], int left, int right) { if (left ) { int pivotIndex = ...
在IT领域,排序算法是计算机科学中的基础但至关重要的部分,尤其在数据处理和数据分析中起着关键作用。本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并...
通过阅读和分析这些代码,可以深入理解各种排序算法的内部工作原理,以及如何在不同层面(软件和硬件)实现它们。同时,这也为优化排序算法提供了实践机会,比如在特定硬件平台上优化性能,或者在保证正确性的前提下...
在计算机科学领域,排序算法是数据结构与算法分析中的核心部分。它们用于对一组数据进行排列,以便于后续处理或优化查找效率。本资源“各种排序算法的实验(源代码+实验报告)”提供了一个全面的平台,用C++语言实现...
### 各类排序算法分析比较特点复杂度分析 #### 排序类别 排序算法可以根据不同的标准进行分类。根据数据结构可以分为基于数组的排序和基于链表的排序;按照是否利用额外存储空间可分为原地排序和非原地排序;根据...
本资源包含快速排序、希尔排序、冒泡排序、插入排序等六种常见的内部排序算法的性能分析,通过源代码和相关文档,我们可以深入理解这些算法的工作原理以及它们在不同情况下的性能表现。 1. **快速排序**:由C.A.R. ...
在计算机科学中,排序算法是数据结构领域的重要组成部分,它涉及到如何有效地重新排列一组数据,使其...在掌握这些基本算法后,还可以探索其他高级排序算法,如归并排序、计数排序、基数排序等,以应对更多样化的需求。
在数据结构中,排序算法是最基本也是最重要的一部分。各种排序算法的性能和选择直接影响着数据处理的效率和准确性。本文将对快速排序、归并排序、堆排序等常见排序算法进行比较和分析,探讨它们的优缺点和适用场景。...
本文将深入探讨在C语言中实现的几种基本排序算法,包括冒泡排序、插入排序、选择排序、快速排序、希尔排序以及归并排序。这些算法各有优劣,适用于不同的场景。 1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单的...
以下是标题"java实现的八种基本排序算法(有注释)"所涵盖的八种排序算法的详细说明: 1. **冒泡排序(Bubble Sort)**: 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换位置,使最大或最小的元素逐渐...
《数据结构:经典排序算法分析与实现》 排序算法是计算机科学中不可或缺的一部分,它用于组织和优化数据,提高数据处理效率。本文将深入探讨六种经典的排序算法:选择排序、直接插入排序、冒泡排序、希尔排序、快速...
二、基本排序算法 1. 冒泡排序:通过不断交换相邻的逆序元素来逐渐将大元素“冒”到数组末尾。时间复杂度为O(n^2)。 2. 插入排序:将每个元素插入到已排序部分的正确位置,适合小规模或近似有序的数组,时间复杂度为...