一直以来就很想整理一下基本的算法实现,工作太忙一直没有来得及整理。
基本排序算法:
首先:代码实现
一、直接插入排序
二、冒泡排序
三、直接选择排序
四、希尔排序
五、快速排序
六、归并排序
七、堆排序
八、总结
首先:代码实现
1.algorith.h文件
#include <iostream> #include <string> #include <vector> #include <map> #include <math.h> #include <fstream> #include <io.h> #include <cstdlib> #include <time.h> #include <sstream> #include <time.h> #include <iostream> #include <string> #include <set> using namespace std; namespace algorith{ class CAlgorith { public: CAlgorith(void); public: ~CAlgorith(void); public: //直接插入排序 void swap(int array[],int i,int j); void insertSort(int array[],int n); //冒泡排序 void bubbleSort(int array[],int n); //直接选择排序 void selectionSort(int array[],int n); //希尔排序 void shellSort(int array[],int n); //快速排序 int partition(int array[],int left,int right); void quickSort(int array[],int left,int right); void quickSort1(int array[],int left,int right); //归并排序 void merge(int array[],int tempArray[],int left,int right,int middle); void mergeSort(int array[],int tempArray[],int left,int right); //堆排序 void maxHeap(int array[],int n); //用已有数组初始化一个最大堆 void buildHeap(); //构建最大堆 void siftDown(int index); //向下筛选法 void swap(int index1,int index2); //交换位置为index1与index2的元素 void removeMax(); //删除堆顶的最大值--与数组最后一个元素交换位置并重新构建最大堆 int leftChild(int index); //返回左孩子的位置 int rightChild(int index); //返回右孩子的位置 private: //关于树 set<string> m_setDeleteForm; int size; //最大堆的元素数目 int *array;//最大堆数组的首地址指针 }; }
2.algorith.cpp文件
#include "algorith.h" using namespace algorith; algorith::CAlgorith::CAlgorith(void) { } algorith::CAlgorith::~CAlgorith(void) { } //交换两个元素的位置 void algorith::CAlgorith::swap(int array[],int i,int j) { int tmp=array[i]; array[i]=array[j]; array[j]=tmp; } void algorith::CAlgorith::insertSort(int array[],int n) { //第一层for循环 for (int i=1;i<n;i++) { //关键的第二层for循环 for (int j=i;j>0;j--) { //如果后者大于前者,交换位置-----降序 if (array[j] > array[j-1]) { swap(array,j,j-1); } else break; } } } //冒泡排序 void algorith::CAlgorith::bubbleSort(int array[],int n) { for (int i =0;i<n-1;i++) { for (int j=n-1;j>i;j--) { //依次比较,把大的放在前面去 if (array[j] < array[j-1]) { swap(array,j,j-1); } } } } //选择排序,选择最小的放在前面 void algorith::CAlgorith::selectionSort(int array[],int n) { for(int i =0;i<n-1;i++) { int minimum = i; for (int j = i+1;j<n;j++) { if (array[minimum] >array[j]) { minimum = j; } } swap(array,i,minimum); } } /*先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。 1、先在各组内进行直接插人排序; 2、然后取第二个增量d2<d1重复上述的分组和排序, 3、直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。 */ void algorith::CAlgorith::shellSort(int array[],int n) { for (int avg = n/2;avg>0;avg/=2) { for(int i =0;i<avg;i++) { for (int j= i+avg;j<n;j+=avg) { for (int k=j;k>0;k-=avg) { if (array[k] < array[k-1]) { swap(array,k,k-1); } } } } } } int algorith::CAlgorith::partition(int array[],int left,int right) { int mid = (left + right)/2; int tmp = array[mid]; swap(array,mid,right); int i = left; int j = right; while(1) { //i指针向右移动,直到找到一个大于轴值的值 if(i==j) { array[i] = tmp; return i; } if (array[i] > tmp) { array[j] = array[i]; j--; break; } i++; } while(1) { /*如果i与j相遇则确定轴值位置,将其返回*/ if(i==j) { array[j]=tmp; return j; } if(array[j]<tmp) { array[i]=array[j]; i++; break; } j--; } } //快速排序 void algorith::CAlgorith::quickSort(int array[],int left,int right) { if(right<=left) return; int pivot=partition(array,left,right); quickSort(array,left,pivot-1); quickSort(array,pivot+1,right); } //快速排序 void algorith::CAlgorith::quickSort1(int array[],int left,int right) { if(left < right){ int key = array[left]; int low = left; int high = right; while(low < high){ while(low < high && array[high] > key){ high--; } array[low] = array[high]; while(low < high && array[low] < key){ low++; } array[high] = array[low]; } array[low] = key; quickSort1(array,left,low-1); quickSort1(array,low+1,right); } } //归并排序 void algorith::CAlgorith::merge(int array[],int tempArray[],int left,int right,int middle) { int index1 = left; int index2 = middle +1; int i; for (i = left;(index1<=middle) &&(index2 <=right);i++) { if (array[index1] < array[index2]) { tempArray[i] = array[index1++]; } else { tempArray[i] = array[index2++]; } } while(index1 <= middle) { tempArray[i++] = array[index1++]; } while(index2 <= right) { tempArray[i++]= array[index2++]; } for(int i = left;i<= right;i++) { array[i] = tempArray[i]; } } //归并排序 void algorith::CAlgorith::mergeSort(int array[],int tempArray[],int left,int right) { if (left < right) { int middle = (left + right)/2; mergeSort(array,tempArray,left,middle); mergeSort(array,tempArray,middle+1,right); merge(array,tempArray,left,right,middle); } } //堆排序 void algorith::CAlgorith::maxHeap(int array[],int n) { this->array=array; size=n; buildHeap(); } void algorith::CAlgorith::buildHeap() { for(int i=size/2-1;i>=0;i--) siftDown(i); } void algorith::CAlgorith::siftDown(int index) { int max_index=leftChild(index); while(max_index<size) { if(max_index<size-1&&array[rightChild(index)]>array[max_index]) max_index++; if(array[index]>array[max_index]) break; swap(index,max_index); index=max_index; max_index=leftChild(index); } } void algorith::CAlgorith::swap(int index1,int index2) { int temp=array[index1]; array[index1]=array[index2]; array[index2]=temp; } void algorith::CAlgorith::removeMax() { swap(0,size-1); size--; siftDown(0); } int algorith::CAlgorith::leftChild(int index) { return index*2+1; } int algorith::CAlgorith::rightChild(int index) { return index*2+2; }
3.mainTest.cpp文件
#include "algorith.h" using namespace algorith; int main(int argc,char * argv[]) { CAlgorith calgorith; //int array[5]={3,1,2,5,4}; int array[8]={6,8,7,3,1,2,5,4}; //calgorith.insertSort(array,5); //calgorith.selectionSort(array,5); //calgorith.shellSort(array,5); //calgorith.quickSort1(array,0,7); int tempArray[8]; calgorith.mergeSort(array,tempArray,0,7); for(int i=0;i<8;i++) cout<<array[i]<<" "; cout<<endl; system("pause"); }
一、直接插入排序
每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中;
第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;
依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。
二、冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序的最大时间代价,最小时间代价和平均时间代价均为θ(n²)。
冒泡排序算法的运作如下:
1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
三、直接选择排序
选择排序的最大时间代价,最小时间代价和平均时间代价均为θ(n²)。选择排序不依赖于原始数组的输入顺序。
四、希尔排序
增量为2的shell排序的时间代价可以达到θ(n的3/2次方),有的增量可以达到θ(n的7/6次方),很接近θ(n)。
希尔排序:将无序数组分割为若干个子序列,子序列不是逐段分割的,而是相隔特定的增量的子序列,对各个子序列进行插入排序;然后再选择一个更小的增量,再将数组分割为多个子序列进行排序......最后选择增量为1,即使用直接插入排序,使最终数组成为有序。
增量的选择:在每趟的排序过程都有一个增量,至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序);根据增量序列的选取其时间复杂度也会有变化,这个不少论文进行了研究,在此处就不再深究;本文采用首选增量为n/2,以此递推,每次增量为原先的1/2,直到增量为1;
下图详细讲解了一次希尔排序的过程:
五、快速排序
快速排序的最大时间代价为θ(n²),最小时间代价为θ(n*logn),平均时间代价为θ(n*logn)。
基本思想是:
1.先从数列中取出一个数作为基准数
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
3.再对左右区间重复第二步,直到各区间只有一个数
六、归并排序
归并排序的最大时间代价,最小时间代价和平均时间代价均为θ(n*logn)。归并排序不依赖于原始数组的有序程度。
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
七、堆排序
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆):
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;
2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
七、总结
稳定的排序算法:
冒泡排序(bubble sort) — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 (insertion sort)— O(n2)
桶排序 (bucket sort)— O(n); 需要 O(k) 额外记忆体
归并排序 (merge sort)— O(n log n); 需要 O(n)额外记忆体
原地归并排序 — O(n2)
二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体
基数排序 (radix sort)— O(n·k); 需要 O(n) 额外记忆体
不稳定的排序算法:
选择排序 (selection sort)— O(n2)
希尔排序 (shell sort)— O(n log n)
Comb sort — O(n log n)
堆排序 (heapsort)— O(n log n)
Smoothsort — O(n log n)
快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序
一般来说:存在不相邻交换的排序算法是不稳定的,相邻交换的排序算法是稳定的;对于相邻交换的稳定排序算法,通过控制交换条件可以转换成不稳定排序算法;冒泡、插入、归并和基数排序是稳定的;选择、快速、希尔和堆排序是不稳定的。
相关推荐
C++是广泛应用的编程语言,能够提供高效的性能,因此C++实现FP-Growth算法具有很高的实用价值。 FP-Growth的核心思想是通过构建一个FP树(Frequent Pattern tree)来存储频繁项集,并利用这个树结构来挖掘出所有的...
《C++算法-图算法(第三版)》是一本深入探讨C++编程语言在实现图算法方面的专业书籍。作为第三版,它很可能包含了最新的研究进展和技术改进,旨在为读者提供全面且更新的知识体系。该书可能涵盖了从基础理论到高级...
"各种排序算法时间性能的比较"这个程序文件可能是用C++语言实现的,C++以其高效和灵活性成为实现算法的常用语言。在这个程序中,应该包含了各种排序算法的函数实现,并且有一个主程序用于测试和比较这些排序算法的...
**C++实现的FP-Growth算法** FP-Growth算法是一种高效的数据挖掘技术,主要用于关联规则学习,即在大规模数据集中发现频繁项集。这个算法在处理大数据量时表现出了较高的性能,因为它避免了构建和搜索全频繁项集的...
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
用c++实现的快速排序算法 算法实现的简单易懂
本文将深入探讨C++实现的几种常见排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序以及堆排序。 1. **冒泡排序**: 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果...
本文将探讨如何使用这两种语言实现几种基本的排序算法:冒泡排序、选择排序,以及两种全比较排序(并行和串行)。 首先,让我们了解一下排序算法。排序是计算机科学中最基础的操作之一,它涉及到将一组数据按照特定...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过选取一个“基准”元素,将数组分为两个子数组,使得左边的元素都小于基准,右边的元素都大于基准,然后对这...
本资源"总结了各种排序算法,并用C++代码实现,并有演示",提供了丰富的学习材料,包括不同类型的排序算法以及它们的C++实现,还有可能的可视化演示,帮助理解每种算法的工作原理。 首先,让我们逐一了解常见的排序...
本主题聚焦于使用C++实现六种不同的排序算法,并应用于四种不同类型的数据。这些排序算法包括了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,它们各自有其独特的性能特征和适用场景。以下是对这六种...
算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ...
本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
数据结构课程设计中,C++实现的八种排序算法涵盖了数据结构的核心概念,这些排序算法在实际编程中具有广泛的应用。下面将详细解释每一种排序算法的设计思想和性能特点。 1. **交换排序**: - **冒泡排序**:通过...
这里我们将深入探讨七种常用的排序算法,并通过C++语言实现它们。这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之...
C++ STL,全称为Standard Template Library(标准模板库),是C++编程语言中的一部分,它提供了丰富的容器、迭代器、算法和函数对象等组件,极大地简化了数据结构和算法的实现。余文溪的《C++ STL--数据结构与算法...
然而,了解并手动实现这些基本排序算法有助于深入理解它们的工作原理,同时在特定场景下优化性能。 比较这些排序算法的效率时,通常考虑以下因素: 1. **时间复杂度** - 描述算法运行所需的步骤数量与输入规模的...
尽管冒泡排序的时间复杂度较高,但在教学和理解排序算法的基本原理时非常有用。在实际应用中,更高效的排序算法如快速排序、归并排序和堆排序通常更受欢迎,尤其是在处理大数据集时。不过,了解和掌握冒泡排序有助于...
数据结构课程设计,C语言,七大排序算法比较