本文主要是介绍数据结构:冒泡排序,选择排序,插入排序,希尔排序的实现分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
✨✨小新课堂开课了,欢迎欢迎~✨✨
🎈🎈养成好习惯,先赞后看哦~🎈🎈
所属专栏:数据结构与算法
小新的主页:编程版小新-CSDN博客
1.冒泡排序
1.1算法思想
冒泡排序的基本思想就是,遍历原数组的元素,比较相邻的两个元素,如果这两个元素的顺序不对,就是把这两个元素交换,直到都不需要交换的时候,排序结束。
1.2具体步骤
比较相邻的两个元素,把大的(小的)往后换,就这样重复此步骤,每遍历完数组一次,就能将最大的(最小的)元素放在最后。重复遍历该数组,直至都不需要交换的时候,排序就结束了。
1.3动图演示
1.4代码实现
void Swap(int*a,int*b)
{int tmp = *a;*a = *b;*b = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int len)
{for (int i = 0; i < len - 1; i++)//比较次数{for (int j = 0; j < len-1-i; j++)//单趟比较{if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}}
}
有的时候不用遍历数组len次,排序就已经排好了,我们知道遍历完数组一次后,如果不存在交换,那就不用再继续比较了。此时排序已经排好了。
优化:
void Swap(int*a,int*b)
{int tmp = *a;*a = *b;*b = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int len)
{int flag = 0;for (int i = 0; i < len - 1; i++)//比较次数{for (int j = 0; j < len-1-i; j++)//单趟比较{if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);flag = 1;}}if(flag ==0)//未发生交换,排序已经完成break;}
}
1.5复杂度分析
时间复杂度:这里很容易就能看出来是O(N^2)。以最坏的情况来看,n-1+n-2+n-3+……+2+1=n*(n-1)/2。
空间复杂度: 因为没有额外的开空间,所以空间复杂度为O(1)。
1.6稳定性分析
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
简而言之,相同值相对位置不变称之为稳定。
冒泡排序是相邻位置的元素比较,决定交不交换,一样的元素,在排序过程中相对位置不会发生变化,因此冒泡排序是稳定的。
2.选择排序
2.1算法思想
遍历原数组,找出最小或者最大的那个元素,与起始位置或则末尾的元素交换,每遍历完一次,起始位置向后移(末尾的位置往前移),当起始位置移到最后一个位置时(末尾位置移到数组的第一个元素的位置时),排序结束。
2.2具体步骤
遍历数组,找到最大或者最小的元素,与起始位置交换。
从剩余的元素中找继续找最大或最小的元素,排到已排序序列的末尾。
以此类推,直到所有的元素都排列完毕。
2.3动图演示
2.4代码实现
基于动态演示实现的代码:
void SelectSort(int* arr, int len)//选择排序
{for (int i = 0; i < len - 1; i++)//起始位置{int mini = i;for (int j = i + 1; j < len; j++)//寻找最小元素{if (arr[j] < arr[mini]){mini = j;}}swap(&arr[mini], &arr[i]);}
}
上面的代码效率比较低,我们在遍历一遍数组的时候,可以找到该数组中最大和最小的元素,让最大的元素与end交换,最小的元素与begin交换,不断的这样缩小区间,完成排序。
这里要注意的是,我们在交换的时候,可能会改变最大或最小元素的位置 。
//选择排序void Swap(int*a,int*b)
{int tmp = *a;*a = *b;*b = tmp;
}void SelectSort(int* arr, int len)
{int begin = 0;int end = len - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <=end; i++){//遍历一遍找最大和最小if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(&arr[begin], &arr[mini]);if (maxi == begin)//如果begin和maxi重合,就要对maxi更正{maxi = mini;}Swap(&arr[end], &arr[maxi]);begin++;end--;}
}
2.5复杂度分析
时间复杂度:优没优化,算时间复杂度的时候都是等差数列,时间复杂度为O(N^2)。
空间复杂度:没有额外开辟空间,因此空间复杂度为O(N)。
2.6稳定性分析
3.插入排序
3.1算法思想
把待排元素逐一与已排序的部分元素进行比较,把它插入到已排序序列中的适当位置,直到把元素全部插入完毕。
3.2具体步骤
把第一个元素看成有序序列,从第二个元素开始,将该元素与前面已排好序的元素比较,如果该元素比较小,就将前面的元素依次往后移动一位,将该元素插入到腾出的位置上。
重复上面的插入过程,直至整个序列都被排序完成。
3.3动图演示
3.4代码实现
// 插入排序
void InsertSort(int* a, int n)
{//【0-end】有序,将end+1的值插入到区间内,形成新的区间for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];//往后移end--;}else{break;//找到合适的位置了//也有可能合适的位置就是数组的起始位置,没有进break,此时end为-1越界,在// end+1的位置插入,就是把该元素插入到起始位置}}a[end + 1] = tmp;//在腾出来的位置插入该元素}}
3.5复杂度分析
时间复杂度:以最坏的情况,逆序来算,移动的次数是等差数列的前n-1项和,O(N^2)。
空间复杂度:没有额外开辟空间,空间复杂度为O(1)。
3.6稳定性分析
插入排序不会改变相同元素的相对位置,在前面的和在后面的那个在插入到腾出的位置后,还是一前一后。因此插入排序稳定。
4.希尔排序
4.1算法思想
希尔排序是对插入排序的改进。它先将整个待排的序列分割成若干个子序列,对每一个子序列分别进行插入排序,然后不断缩小缩小子序列的间隔,重复这个过程直至间隔为1 时进行一次完整的插入排序。
4.2具体步骤
希尔排序分为两步:1.预排序(使数组接近有序) 2.插入排序
选取一个gap,间隔gap个数据为一组,把整个数组进行分组,一共gap组。
以gap为基准,对其进行插入排序。
不断缩小gap,直至gap为1,进行一次完整的插入排序。
gap>1时是在进行预排序,gap==1是在进行直接插入排序。
4.3动图演示
4.4代码实现
// 希尔排序
//希尔排序分为两步:第一步是预排序(使其接近有序),第二步是进行插入排序
void ShellSort(int* a, int n)
{int gap = n;//gap代表每间隔gap个为一组即一共分成gap组while (gap > 1){//gap>1是进行预排序//gap==1是在进行插入排序gap = gap / 3 + 1;//+1是保证最后一组gap一定为1,for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];//i之所以小于n-gap;是防止这里越界while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
4.5复杂度分析
时间复杂度:希尔排序的时间复杂度可以直接记,因为比较难算。O(N^1.3)
空间复杂度:没有额外开辟空间,空间复杂度为O(1)。
4.6稳定性分析
在排序过程中,可能相同数据分到不同的组,这个无法控制,因此希尔排序不稳定。
这篇关于数据结构:冒泡排序,选择排序,插入排序,希尔排序的实现分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!