【算法导论笔记】插入排序 && 归并排序

小灰灰 2022-05-08 10:06 208阅读 0赞

插入排序 时间复杂度 O(n^2)

#include "pch.h"
    #include <iostream>
    
    void insectionSort();
    
    int origin[] = { 12, 15, 3, 2, 31, 34, 18, 9, 99, 121, 56 };
    
    int main()
    {
    	insectionSort();
    	for (int i = 0; i < sizeof(origin) / sizeof(origin[0]); i++)
    	{
    		std::cout << origin[i] << std::endl;
    	}
    }
    
    void insectionSort()
    {
    	for (int i = 1; i < sizeof(origin) / sizeof(origin[0]); i++)
    	{
    		// 标记第 i 个做插入排序的元素，0 - i-1 已经是有序序列 
    		int temp = origin[i];
    		// 从 i-1 开始和前面排序序列比较，看在哪里插入
    		int j = i - 1;
    		for (; j >= 0 && origin[j] > temp; j--)
    		{
    			origin[j + 1] = origin[j];
    		}
    		// 最终的 j 标识插入的前一个位置
    		origin[j + 1] = temp;
    	}
    }

归并排序 时间复杂度 O(nlogn)

#include "pch.h"
    #include <iostream>
    
    void mergeSort(int * A, int number);
    void merge(int * A, int * L, int lIndex, int * R, int rIndex);
    
    int main()
    {
    	int sequence[] = { 12, 15, 3, 2, 31, 34, 18, 9, 99, 121, 56 };
    	int sizeOfElements = sizeof(sequence) / sizeof(sequence[0]);
    	mergeSort(sequence, sizeOfElements);
    
    	for (int i = 0; i < sizeOfElements; i++)
    	{
    		std::cout << sequence[i] << std::endl;
    	}
    }
    
    /* 归并排序主代码 */
    void mergeSort(int * A, int size)
    {
    	if (size < 2) return;
    	int mid = size / 2;
    	int *L, *R;
    
    	L = new int[mid];
    	R = new int[size - mid];
    
    	for (int i = 0; i < mid; i++) L[i] = A[i];
    	for (int i = mid; i < size; i++) R[i - mid] = A[i];
    
    	mergeSort(L, mid);
    	mergeSort(R, size - mid);
    	merge(A, L, mid, R, size - mid);
    
    	delete[] L;
    	delete[] R;
    }
    
    /* 合并两个已排序的数组，最终返回给 A */
    void merge(int * A, int * L, int lSize, int * R, int rSize)
    {
    	int lIndex = 0, rIndex = 0;
    
    	for (int i = 0; i < lSize + rSize; i++)
    	{
    		if (lIndex >= lSize)
    		{
    			A[i] = R[rIndex++];
    			continue;
    		}
    		if (rIndex >= rSize)
    		{
    			A[i] = L[lIndex++];
    			continue;
    		}
    
    		if (L[lIndex] < R[rIndex]) 
    		{
    			A[i] = L[lIndex++];
    		}
    		else if (L[lIndex] == R[rIndex])
    		{
    			A[i] = L[lIndex++];
    		}
    		else if (L[lIndex] > R[rIndex])
    		{
    			A[i] = R[rIndex++];
    		}
    	}
    }