摘要:本文主要向大家介绍了C/C++知识点之c++ 6种排序算法 源代码,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之c++ 6种排序算法 源代码,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
// sort.cpp : 定义控制台应用程序的入口点。//#include ""stdafx.h""#include <iostream>using namespace std;template <typename T>void print(T* &arr,int len) { for (int i=0;i<len;i++) { cout<<*(arr+i)<<' '; } cout<<endl; }//简单选择排序/* 1.i=[0,len-1),j=[i+1,len-1]数组第i元素值与j元素值比较,大于交换i与j的元素值 2.j+=1 重复第一步直到 j == len 3.i+=1 重复第一步 直到 i == len - 1 */template <typename T>void select_sort(T* &array,int len){ if (NULL == array) { cout<<""#ERROR ""<<__FILE__<<"" Line:""<<__LINE__<<"" null point error""<<endl; return; } for (int i=0; i<len-1; i++) for (int j=i+1;j<len;j++) if (array[i] > array[j]) swap(array[i],array[j]); }//冒泡排序/* 1.BUBBLE相邻2个元素比较,大则交换 每一次使得最大的值到最上面 */template <typename T>void bubble_sort(T* &array,int len){ if (NULL == array) { cout<<""#ERROR ""<<__FILE__<<"" Line:""<<__LINE__<<"" null point error""<<endl; return; } bool flag; for (int i=0; i<len-1; i++) { flag = true; for (int j=0;j<len-i-1;j++) if (array[j] > array[j+1]) { flag = false; swap(array[j],array[j+1]); } if (flag) break; } }//插入排序/* 1.i属于[1,len)从i位置往前判断j属于[0,i) 则后一个元素与前一个相比小于则替换,大于等于退出第一个循环 */template <typename T>void insert_sort(T* &array,int len){ if (NULL == array) { cout<<""#ERROR ""<<__FILE__<<"" Line:""<<__LINE__<<"" null point error""<<endl; return; } for (int i=1; i<len; i++) { for (int j=i;j;j--) { if (array[j] >= array[j-1]) break; swap(array[j],array[j-1]); } } }//归并排序/* 用到二分思想将数据递归成左右2边得到链表A,B 1.链表A,B用链表归并来得到新的有序链表 */template <typename T>void merge(T* &array,int left,int mid,int right,T* temp){ int i = left; int j = mid+1; int k = 0; while (i<=mid && j<=right) { if (array[i] > array[j]) temp[k++] = array[j++]; else temp[k++] = array[i++]; } //追加最后 while (i <= mid) temp[k++] = array[i++]; while (j<=right) temp[k++] = array[j++]; //临时变量copy到元素组中 k = 0; while(left<=right)//没注意写成k<=right 调试了半天。 数据变成大数考虑是否赋值越界 array[left++] = temp[k++]; }template <typename T>void merger_sort(T* &array,int left,int right,T* temp){ if (left < right) { int mid = (left + right)/2; merger_sort<T>(array,left,mid,temp);//排序左边子序列 merger_sort<T>(array,mid+1,right,temp);//排序右边子序列 merge<T>(array,left,mid,right,temp);//左右2边归并 } }template <typename T>void merger_sort(T* &array,int len){ if (NULL == array) { cout<<""#ERROR ""<<__FILE__<<"" Line:""<<__LINE__<<"" null point error""<<endl; return; } T* temp = new T[len]; merger_sort<T>(array,0,len-1,temp); if (NULL != temp) { delete[] temp; temp = NULL; } }//快排/* (一)挖坑填坑 1.以第一个元素为基准X 初始值前缀i = left 后缀j = right 2.后缀从后往前查找j元素值 < X;i处 赋值 j元素值 3.前缀从前往后查找i元素值 > X;j处 赋值 i元素值 重复第2,3步 (二)分治 1.左边[left,i)执行(一) 2.右边(i,right]执行(一) 递归执行1,2 */template <typename T>int dig_fil(T* &array,int left,int right){ T X = array[left]; int i = left; int j = right; while (i<j) { while(j>i && array[j] >= X)j--; if (j>i)//只有满足后缀大于前缀才能赋值 不然会数组越界 { array[i] = array[j]; i++; } while(i<j && array[i] < X) i++; if (i<j) { array[j] = array[i]; j--; } } array[i] = X; return i; }template <typename T>void quick_sort(T* &array,int left,int right){ if (left < right) { int mid = dig_fil<T>(array,left,right); quick_sort(array,left,mid-1); quick_sort(array,mid+1,right); } }template <typename T>void quick_sort(T* &array,int len){ if (NULL == array) { cout<<""#ERROR ""<<__FILE__<<"" Line:""<<__LINE__<<"" null point error""<<endl; return; } quick_sort(array,0,len-1); }//堆排序/* 堆排序采用完全二叉树 1.从所有非叶节点中构建最大堆 2.交换堆顶与最后一个元素 3.对所有[0,len-1)执行第 1,2步 */template <typename T>void adjust(T* &array,int sign,int len){ T temp = array[sign]; //每一次循环都更新该父节点为根的完全二叉树最大堆 for (int i = sign * 2 + 1; i < len; i = i * 2 + 1){ if (i + 1 < len && array[i + 1] > array[i]) i++; //判断子节点 大于父节点 if (array[i] > temp){ array[sign] = array[i]; sign = i; } } array[sign] = temp; }template<typename T>void heap_sort(T* &array,int len){ //1.从所有非叶子节点 构建初始大顶堆 for (int i = len / 2 - 1; i >= 0; i--){ adjust(array, i, len); } // for (int i = len - 1; i; i--){ //2.交换最大堆 和 相对的最后一个元素 swap(array[i],array[0]); //3.重新调整堆结构 adjust(array, 0, i); } }int _tmain(int argc, _TCHAR* argv[]) { int a[] = {1,5,4,9,0,2,3,6,8,7}; int* pa = a; //select_sort<int>(pa,10); //bubble_sort<int>(pa,10); //insert_sort<int>(pa,10); //merger_sort<int>(pa,10); //quick_sort<int>(pa,10); //heap_sort(pa,10); print<int>(pa,10); getchar(); return 0; }
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号