排序算法整理

在这里插入图片描述

快速排序

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;
}