八大排序

GuoTianyu2025-08-202025-08-20

八大排序

插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
其他排序：归并排序、基数排序、计数排序

直接插入排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

//直接插入排序 
void InsertSort(int *array,int n)
{
	int i,j;
	for(i=1;i<n;i++)
	{
		int temp=array[i];
		for(j=i-1;j>=0&&array[j]>temp;j--)//array[j]<temp
		{
			array[j+1]=array[j];
		}
		array[j+1]=temp;
	}
}

折半插入排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

//折半插入排序
void BinInsertSort(int *array,int n)
{
	int j,i,high,low,mid;
	for( i=1;i<n;i++)
	{
		int temp=array[i];
		low=0,high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(array[mid]>temp)high=mid-1; //array[j]<temp
			else low= mid+1;
		}
		for(j=i-1;j>=high+1;j--)
		{
			array[j+1]=array[j];
		}
		array[j+1]=temp;
		
	}
}

希尔排序

时间复杂度：O(n²)、O(n^1.3)
空间复杂度：O(1)

//希尔排序
void ShellSort(int *array,int n)
{
	int dk,i,j;
	for(dk=n/2;dk>=1;dk=dk/2)
	{
		for(i=dk;i<n;i++)
		{
			if(array[i]<array[i-dk]) 
			{
				int temp = array[i];
				for(j=i-dk;j>=0&&array[j]>temp;j-=dk)
				{
					array[j+dk]=array[j];
				}
				array[j+dk]=temp;
			}
		}
	}
}

冒泡排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

//冒泡排序 
void BubbleSort(int *array,int n)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n-1-i;j++)
		{
			if(array[j]>array[j+1])//array[j]<array[j+1]
			{
				int temp = array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
			}
		}
	}
}

快速排序

时间复杂度：O(n²)、O(nlogn)
空间复杂度：O(n)、O(logn)
稳定性：不稳定

//快速排序
int Partition(int *array,int low,int high)
{
	int pivot=array[low];
	while(low<high)
	{
		while(low<high&&array[high]>=pivot)high--;
		array[low]=array[high]; 
		while(low<high&&array[low]<=pivot)low++;
		array[high]=array[low]; 
	}
	array[low]=pivot;
	return low;
}
void QuickSort(int *array,int low,int high)
{
	if(low<high)
	{
		int pivotpos=Partition(array,low,high);
		QuickSort(array,low,pivotpos-1);
		QuickSort(array,pivotpos+1,high);
	}
}

简单选择排序

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定、

//选择排序
void SelectSort(int *array,int n)
{
	//经典选择排序 
	for(int i=0;i<n;i++)
	{
		int min = i ;
		for(int j=i+1;j<n;j++)
		{
			if(array[min]>array[j])min=j;
		}
		if(i!=min)
		{
			int temp = array[min];
			array[min]=array[i];
			array[i]=temp;
		}
	 } 
	 
	 //及时交换选择排序
	 /*
	 for(int i=0;i<n;i++)
	 {
	 	for(int j=i+1;j<n;j++)
	 	{
	 		if(array[i]>array[j])
	 		{
	 			int temp = array[i];
				array[i]=array[j];
				array[j]=temp;
			 }
		 }
	 }*/
	 
}

堆排序

时间复杂度：建堆O(n)+排序O(nlogn) = O(nlogn)
空间复杂度：O(1)
稳定性：不稳定

//堆排序
// 将以 k 为根的子树调整成大根堆，堆的有效范围 [0..heapSize-1]
void HeadAdjust(int *array, int k, int heapSize)
{
    int temp = array[k];              // 保存根结点值
    for (int i = 2 * k + 1;           // i 指向左孩子（0 下标时：左孩子=2*k+1）
         i < heapSize;                // 未越界
         i = 2 * i + 1)               // 继续向下
    {
        if (i + 1 < heapSize &&       // 右孩子存在
            array[i] < array[i + 1])  // 右孩子更大
            ++i;                      // 让 i 指向更大的孩子

        if (temp >= array[i])         // 根已最大，结束
            break;

        array[k] = array[i];          // 将大孩子上浮
        k = i;                        // 继续向下筛选
    }
    array[k] = temp;                  // 把 temp 放到最终位置
}

// 建大根堆（0 下标）
void BuildMaxHeap(int *array, int n)
{
    for (int i = n / 2 - 1; i >= 0; --i)   // 从最后一个非叶结点开始
        HeadAdjust(array, i, n);
}

// 堆排序（0 下标）
void HeapSort(int *array, int n)
{
    BuildMaxHeap(array, n);          // 建堆

    for (int i = n - 1; i > 0; --i)  // 依次把最大元素放到末尾
    {
        std::swap(array[0], array[i]); // 堆顶与末尾交换
        HeadAdjust(array, 0, i);        // 对 [0..i-1] 重新调整为大根堆
    }
}

归并排序

时间复杂度：O(logn)
空间复杂度：O(n)
稳定性：稳定

//归并排序
int w[100];
void MergeSort(int *array,int low,int high)
{
	if(low>=high)return;
	int mid=(low+high)/2;
	MergeSort(array,low,mid);
	MergeSort(array,mid+1,high);
	int i=low,j=mid+1,k=0;
    while(i<=mid&&j<=high)
    {
        if(array[i]<array[j])
        {
            w[k++]=array[i++];
        }else
        {
            w[k++]=array[j++];
        }
    }
    while(i<=mid)
    {
        w[k++]=array[i++];
    }
    while(j<=high)
    {
        w[k++]=array[j++];
    }
    for(i = low,j=0;i<=high;i++,j++)array[i]=w[j];	
}

测试代码

#include<iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void printArray(int *array,int n)
{
	bool sx=true;
	bool jx=true;
	for(int i=0;i<n;i++)
	{
		if(i!=0)
		{
			if(array[i-1]<array[i])jx=false;
			if(array[i-1]>array[i])sx=false;
		}
		printf("%d ",array[i]);
	}
	if(sx)printf("升序 "); 
	if(jx)printf("降序 "); 
	if(!sx&&!jx)printf("error "); 
	printf("\n");
}

void generateRandomArray(int*& arr, int& size)
{
    // 用当前时间播种（只做一次即可）
    static bool seeded = false;
    if (!seeded) {
        std::srand(static_cast<unsigned>(std::time(nullptr)));
        seeded = true;
    }

    // 动态分配并填充
    arr = new int[size];
    for (int i = 0; i < size; ++i) {
        arr[i] = std::rand() % 100;   // 产生 [-100, 100]
    }
}
void test(int n,int length)
{
	srand(static_cast<unsigned>(time(0))); // 使用当前时间作为种子
	while(n--)
	{
		int* array = nullptr;
		generateRandomArray(array,length);
		
		//InsertSort(array,length);//插入排序 
		//BinInsertSort(array,length);//折半插入排序 
		//ShellSort(array,length);//希尔排序 
		//BubbleSort(array,length);//冒泡排序 
		//SelectSort(array,length);//选择排序 
		 //QuickSort(array,0,length-1); //快速排序 
		//MergeSort(array,0,length-1);//归并排序 
		//HeapSort(array,length);
		printArray(array,length);
		delete array;
	}
 } 
int main()
{
	//测试个数n，以及数组大小length 
	test(10,10);
	return 0;
 }

运行结果

3 3 26 29 42 52 79 87 88 96 升序
10 11 52 61 65 74 79 81 96 98 升序
7 13 21 26 43 47 66 69 82 87 升序
9 19 20 21 27 40 40 72 91 98 升序
5 11 36 42 47 51 65 73 83 90 升序
7 13 17 18 27 27 44 64 70 73 升序
13 16 18 31 51 69 80 80 86 90 升序
27 41 43 47 49 53 65 72 94 96 升序
16 21 31 32 34 48 57 62 70 94 升序
20 37 43 51 52 57 63 77 79 81 升序

--------------------------------
Process exited after 0.3861 seconds with return value 0
请按任意键继续. . .