算法基础：常用的排序算法总结（C++版）

目录

1.冒泡排序

2.插入排序

3.快速排序

4.归并排序

5.希尔排序

6.堆排序

1.冒泡排序

void BubbleSort(int arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length -  i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp;
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}

2.插入排序

void InsertSort(int arr[], int length)
{
	for (int i = 1; i < length; i++)
	{
		int j;
		if (arr[i] < arr[i - 1])
		{
			int temp = arr[i];
			for (j = i - 1; j >= 0 && temp < arr[j]; j--)
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

3.快速排序

快速排序实现的重点在于数组的拆分，通常我们将数组的第一个元素定义为比较元素，然后将数组中小于比较元素的数放到左边，将大于比较元素的放到右边，
这样我们就将数组拆分成了左右两部分：小于比较元素的数组；大于比较元素的数组。我们再对这两个数组进行同样的拆分，直到拆分到不能再拆分，数组就自然而然地以升序排列了。

void swap(int nums[],int i,int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}
int partition(int nums[],int leftBound,int rightBound){
    int left=leftBound;
    int right=rightBound-1;
    int pivot=nums[rightBound];
    while (left<=right){
        while (left<=right&&nums[left]<=pivot)left++;
        while (left<=right&&nums[right]>pivot)right--;
        if(left=rightBound)return;
    int mid= partition(nums,leftBound,rightBound);
    sort(nums,len,leftBound,mid-1);
    sort(nums,len,mid+1,rightBound);
}

4.归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

void merge(int nums[],int left,int right,int rightBound){
    int len=rightBound-left+1;
    int tmpArr[len];
    int x=left,y=right,k=0;
    while (x<=(right-1)&&y<=rightBound){
        tmpArr[k++]=nums[x]<=nums[y]?nums[x++]:nums[y++];
    }
    while (x<=(right-1))tmpArr[k++]=nums[x++];
    while (y<=rightBound)tmpArr[k++]=nums[y++];
    for (int i = 0; i < len; ++i){
        nums[left+i]=tmpArr[i];
    }

}
void sort(int nums[],int left,int right){
    if(left>=right)return;
    int mid=(right+left)/2;
    sort(nums,left,mid);
    sort(nums,mid+1,right);
    merge(nums,left,mid+1,right);
}

5.希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

void swap(int nums[],int i,int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}
void sort(int nums[],int len){
    for (int gap = len/2; gap >0; gap/=2) {
        for (int i = gap; i < len; ++i) {
            for (int j = i; j >=gap; j-=gap) {
                if(nums[j] 
6.堆排序 
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
 
void swap(int nums[],int i,int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}
void heapify(int nums[],int i,int len){
    int left=2*i+1;
    int right=2*i+2;
    int newIndex=i;
    if(leftnums[newIndex]){
        newIndex=left;
    }
    if(rightnums[newIndex]){
        newIndex=right;
    }
    if(newIndex!=i){
        swap(nums,i,newIndex);
        heapify(nums,newIndex,len);
    }


}

void buildMaxHeap(int nums[], int len) {
    for (int i = len/2-1; i >=0; --i){
        heapify(nums,i,len);
    }
}