七大排序算法 ——（冬至快乐）

冬至快乐 ^ _ ^

今天脑子有点乱不知道要干什么，就把自己所学的几种排序算法写一下吧……

---

------七大排序-----

1. 选择排序
2. 冒泡排序（优化写法)
3. 快速排序
4. 插入排序
5. 希尔排序（插入排序优化)
6. 桶排序
7. 归并排序

---

选择排序

在顺序排序基础上进行了改进，使得每一次只交换一次

void SelectionSort(int* arr, int size)		// size 为数组的大小
{
    for(int i = 0; i < size - 1; i++)
    {
        int k = i;		 
        for(int j = i + 1; j < size; j++)
        {
            if(arr[k] > arr[j])			// 标记最大值的下标  
            {
                k = j;
            }
        }
	if(k != i)				// 判断 k 是否改变 若未改变则不用交换
	{
	    swap(arr[k], arr[i]);		// swap 标准库函数 在 命名空间 std中
	}
    }
}

---

冒泡排序（优化写法）

两两交换，第一轮找到最大的元素，有一次没有交换则排序结点（优化）

void BubbleSort(int* arr, int size)
{
    bool flag = false;			
    for(int i = 0; i < size - 1; i++)
    {
        flag = true;
        for(int j = 0; j < size - 1 - i; j++)
        {
            if(arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                
                flag = true;			
            }
        }
        if(!flag)				// 某一次没有交换 数组已经排序
        {
            break;
        }
    }
}

---

快速排序

什么是快速排序我就不说了，直接上代码

两个不同的快速排序方法：

1. 填坑法

//  left  right 为数组下标   确定一个范围   
void QuickSort1(int* arr, int left, int right)
{
    if(left < right)
    {
        int i = left;
        int j = right;
        int value = arr[left];		// 每次以第一个数为 基数

        while(i < j)
        {
            while(i < j && value < arr[j])	// 找到比基数小的数   从右边开始寻找
            {
                j--;
            }
            if(i < j)
            {
                arr[i++] = arr[j]
            }

	    while(i < j && value > arr[i])
	    {
	        i++;
	    }
	    if(i <　j)
	    {
	        arr[j--] = arr[i];
	    }
        }

        arr[i] = value;

	// 递归 分成若干个左右区域
        QuickSort(arr, left, i - 1);
        QuickSort(arr, i + 1, right);
    }
}

2. 直接交换法
找到比基值小的 和大的，直接交换

void QuickSort(int* arr, int left, int right)
{
    if(left < right)
    {
        int i = left;
        int j = right;
        int value = arr[left];

        while(i < j)
        {
            while(i < j && value < arr[j])
            {
                j--;
            }
            while(i < j && value > arr[i])
            {
                i++;
            }
 
            swap(arr[i], arr[j]);		// 直接交换 
        }

        arr[i] = value;
   
        QuictSort(arr, left, i - 1);
        QuictSort(arr, i + 1, right);
    }
}

---

插入排序

确定第一个数，后面的数依次向前比较

void InsertSort(int* arr, int size)
{
    for(int i = 1; i < sze; i++)
    {
        int j = i - 1;
        int temp = arr[i];		// 存储要插入的数  以防止被前一个数覆盖
        
        while(j >= 0 && atemp < arr[j])		// 向前寻找要插入的位置
        {
             arr[j + 1] = arr[j];
             j--;
        }
        
        arr[j + 1] = temp;			// 插入元素
    }
}

---

希尔排序

插入排序的优化版本，性能得到了极大的优化

void ShellSort(int* arr, int size)
{
    //  步长值
    for(int stepValue = size / 5; stepValue > 0; stepValue /= 2)
    {
        for(int i = stepValue; i < size; i++)
        {
            int j = i - stepValue;	
            int temp = arr[i];
            while(j >= 0 && temp < arr[j])
            {
                arr[j + stepValue] = arr[j]
                j -= stepValue;
            }
            arr[j + stepValue] = temp;
        }
    }
}

---

桶排序

以数组下标为元素（桶），进行排序

void BucketSort(int* arr, int size, int max)
{
    vector<int> buckets(max);		// 借助一个容器
    int i,j;
    
    for(i = 0; i < size; i++)
    {           
        buckets[arr[i]]++;		// 相同的数存放在一个桶中
    }
    for(i = 0, j = 0; i < max; i++)
    {
        while(buckets[i]-- > 0)		// 以下标为元素  值为个数
        {
            arr[j++] = i;		
        }        
    }
}

---

归并排序

分而治之的思想

// 合并
void Merge(int* arr, int left, int mid, int right)
{
    int low = left;
    int high = mid + 1;				// 为什么加1 ？   两区域相比   mid + 1 代表第二个区域的第一个元素的下标
    int length = right - left + 1;		// 长度
    
    vector<int> mergeArr(length); 		// 存储合并的两块区域
    int index = 0;
    
    while(low <= mid && high <= right)
    {
        if(arr[low] < arr[high])
        {
            mergeArr[index++] = arr[low++];
        }
        else
        {
            mergeArr[index++] = arr[high++];
        }
    }
    while(low <= mid)
    {
        mergeArr[index++] = arr[low++];
    }
    while(high <=　right)
    {
        mergeArr[index++] = arr[high++];
    }

    // 将容器内排好序的元素 赋给 arr
    for(int i = 0; i < length; i++)
    {
        arr[left + i] = mergeArr[i];
    }
}


void MergeSort(int* arr, int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        // 拆分
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        
        // 合并		合并的同时比较大小
        Merge(arr, left, mid, right);
    }
}

---

作者： 花 梦

时间： 2019.12.12