文章来源地址https://www.toymoban.com/news/detail-800665.html
快速排序
C实现
void fastStore(int *a, int start, int end){
if(start>=end)
return ;
int left=start;
int right=end;
int temp=a[left];//设置基准值temp
while(left < right) //左指针的位置一定小于右指针的位置
{
while(a[right]>temp && left < right)
//左指针要在右指针的左面
{
right--;
}
a[left] = a[right];
left++;
while(a[left] < temp && left < right){
left++;
}
a[right] = a[left];
right--;
a[left] = temp;
}
fastSort(a,start,left-1);
fastSort(a,right+1,end);
}
void FastSort(int *a,int start,int end)
{
if(start>=end)//递归条件
{
return; //跳出递归
}
//初始化左右指针
int left = start;
int right = end;
int temp = a[left]; //基准值
while(left < right)
{
while(a[right]>temp && left < right)
{
right--;
}
a[left] = a[right]; //将右指针的值赋给左指针
left++;
while(a[left]<temp && left<right)
{
left++;
}
a[right] = a[left];
right--;
a[left] = temp; //把基准值赋给左指针
}
FastSort(a,start, left-1); //左面
FastSort(a,right+1, end); //右面
}
C++实现
#include<iostream>
//快排具体实现
template<typename T>
void showNum(T *num,int len)
{
for (int j = 0; j < len; j++)
{
std::cout<<num[j]<<" ";
}
std::cout<<std::endl;
}
template<typename T>
int part(T* arr, int left, int right) //划分函数
{
int i = left;
int j = right;
T fidValue = arr[left];
while (i < j)
{
while (i<j && arr[j]>fidValue) //从右向左开始找一个 小于等于 pivot的数值
{
j--;
}
if (i < j)
{
std::swap(arr[i++], arr[j]); //r[i]和r[j]交换后 i 向右移动一位
}
while (i < j && arr[i] <= fidValue) //从左向右开始找一个 大于 pivot的数值
{
i++;
}
if (i < j)
{
std::swap(arr[i], arr[j--]); //r[i]和r[j]交换后 i 向左移动一位
}
}
return i; //返回最终划分完成后基准元素所在的位置
}
template<typename T>
void fastSort(T *arr,int left,int right)
{
int mid;
if (left < right)
{
mid = part(arr, left, right); // 返回基准元素位置
fastSort(arr, left, mid - 1); // 左区间递归快速排序
fastSort(arr, mid+1, right); // 右区间递归快速排序
}
}
template<typename T>
void Sort(T *num,int len)
{
fastSort(num,0,len-1);
}
int main()
{
int num[] = {4,2,1,6,3,8,12,0,34};
Sort<int>(num,sizeof(num)/sizeof(num[0]));
showNum<int>(num,sizeof(num)/sizeof(num[0]));
std::string str[]={"w ","c ","d ","a "};
Sort<std::string>(str,sizeof(str)/sizeof(str[0]));
showNum<std::string>(str,sizeof(str)/sizeof(str[0]));
return 0;
}
插入排序
#include<stdio.h>
//显示数组
void ShowArray(int *num, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ",num[i]);
}
printf("\n");
}
//插入排序: 与冒泡相反,在开始遍历数据时,就进行数据的排序,遍历后的数据实现有序
/***
* 具体实现:
* 对数据进行遍历,对遍历到某位置的数据,
* 通过临时值,实现与该位置之前的所有数据的比较,
* (因为在循环中,所以,该位置之前的所有数据是有序的)
* 当 该值 大于前一位置的值时,即可,跳出比较循环,并将temp赋给当前位置j
*/
void InsertSort(int *num, int len)
{
for(int i=0;i<len;i++)
{
int temp=num[i]; //一个临时值
int j=i;
for(;j>0;j--){
if(temp<num[j-1]){ //和i位置之前的所有数据进行比较
num[j]=num[j-1]; //把大值放在右面
}
else{ //temp>num[j-1], 即temp大于前一个数
break; //跳出第二层循环,并将当前的j位置的数值置为temp
}
}
num[j]=temp;
}
}
int main()
{
int num[]={2,7,1,4,8,3,9};
InsertSort(num,sizeof(num)/sizeof(num[0])-1);
ShowArray(num,sizeof(num)/sizeof(num[0]));
return 0;
}
冒泡排序
#include<stdio.h>
//显示数组
void ShowArray(int *num, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ",num[i]);
}
printf("\n");
}
//冒泡排序
/**
* 算法思想:
* 通过循环每次比较,将最大值放在最后
* 这样,每次遍历循环的数据个数都会-1
* 最后一个数据无需比较,默认最小值
*/
void BubbleSort(int *num,int size)
{
//遍历,找寻最大值
for (int i = 0; i < size-1; i++) //最后一个数无需比较,自动上浮
{
for (int j = 0; j <size-i-1; j++) //size-i-1:是因为,前i个数据已经排成有序队列,无需再次比较:
{
if (num[j]>num[j+1]) //每一轮比较的最大值都会上浮,即可排除该值,所以-i
{
int tmp = num[j];
num[j]=num[j+1];
num[j+1] = tmp;
}
}
}
}
int main()
{
int num[]={2,7,1,4,8,3,9};
BubbleSort(num,sizeof(num)/sizeof(num[0]));
ShowArray(num,sizeof(num)/sizeof(num[0]));
return 0;
}
选择排序
#include<stdio.h>
//显示数组
void ShowArray(int *num, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ",num[i]);
}
printf("\n");
}
//选择排序 :
/**
* 算法思想:
* 选取左位置的数据为一最小值(或者最大值),与数据进行比较,找到最小值或最大值
* 与当前的i位置的数据进行交换,保证遍历过的数据是有序的
*/
void ChooseSort(int *num, int len)
{
int minnum = 0;
for(int i=0;i<len;i++)
{
minnum = num[i];
for (int j = i+1; j < len; j++)
{
if (num[j]<minnum) //查找最小值,将当前位置的值与num[j]交换
{
int temp = minnum; //选用下标,效率更高,将会减少了交换次数
minnum = num[j];
num[j] = temp;
}
}
num[i]=minnum;
}
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void ChooseSort2(int *num , int len)
{
int i, j, minnum;
for(i = 0; i < len; i++)
{
minnum = i; //下标
for(j = i+1; j<len; j++)
{
if (num[j]<num[minnum]) //查找最小值的下标
minnum = j;
}
swap(&num[minnum],&num[i]);
}
}
int main()
{
int num[]={2,7,1,4,8,3,9};
ChooseSort2(num,sizeof(num)/sizeof(num[0])-1);
ShowArray(num,sizeof(num)/sizeof(num[0]));
return 0;
}
文章来源:https://www.toymoban.com/news/detail-800665.html
到了这里,关于排序算法整理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!