常见排序算法

逃离我推掉我的手 2022-05-11 05:54 305阅读 0赞

### 文章目录 ###

*  排序
 *   *  排序概念
     *  排序算法稳定性
     *  常见排序算法
     *   *  插入排序
         *  选择排序
         *  交换排序
         *  归并排序

# 排序 #

## 排序概念 ##

排序：就是将一组杂乱无章的数据按照一定规律（升序或者降序）组织起来。  
排序码：通常数据元素有多个属性域，其中有一个属性域可用来区分元素，作为排序依据，该域即为排序码。

## 排序算法稳定性 ##

如果在元素序列中有两个元素R\[i\]和R\[j\]，他们的排序码相同，在排序之前R\[i\]在R\[j\]之前。如果排序之后R\[i\]在R\[j\]之前，则称这个排序算法是稳定的，否则这个排序算法不稳定。

**内部排序**：数据元素全部放在内存中的排序  
**外部排序**：数据元素太多，不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

## 常见排序算法 ##

### 插入排序 ###

基本思想：每一步将待排序的元素，按其排序码的大小，插入到已经排好序的一组元素的合适位置上去，直到元素插完为止。

*  直接插入排序

当插入第i个元素时，前面的元素已经排好序，此时用这个数依次往前比较，找到插入位置将该元素插入，原来位置上的元素顺序后移。

#void InsertSort(int*array,int size)
    {
    	int i = 0;
    	for(i=1;i<size;i++)
    	{
    		int k = array[i];//k为待插入元素
    		int end = i-1;
    		//找插入位置
    		while(end >= 0 && k < array[end])
    		{
    			array[end+1] = array[end];//搬移数据
    			end--;
    		}
    		array[end+1] = k;
    	}	
    }

<table> 
 <thead> 
  <tr> 
   <th>应用场景</th> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1.接近有序；2.数据量小</td> 
   <td>O(N<sup>2</sup>)</td> 
   <td>O(1),稳定的排序算法</td> 
  </tr> 
 </tbody> 
</table>

优化  
找位置——二分查找  
搬数据  
插数据

void BinarySearch_InsertSort(int* array,int size)
    {
    	int i = 0;
    	int j = 0;
        for(i=0;i<size;i++)
    	{
            int left=0;
            int right=i-1;
            int temp=array[i];
            while(right>=left)
            {
                int middle=left+(right-left)>>1;
                if(array[middle]>temp)
                    right = middle-1;
                else
                    left = middle+1;
            }
            //每次查找完，left总比right大1
            //查找结果：最后，array[left]总比temp大
            for(j=i-1;j>=left;j--)
                array[j+1]=array[j];//搬移数据
            array[left]=temp;//插入数据
        }
    	return;
    
    }

*  希尔排序

void ShellSort(int* array,int size)
    {
    	
    	int gap = 3;
    	while(gap>=0)
    	{
    		int i = 0;
    		for(i=gap;i<size;i++)
    		{
    			int k = array[i];//k为待插入元素
    			int end = i-gap;
    			//找插入位置
    			while(end >= 0 && k < array[end])
    			{
    				array[end+gap] = array[end];//搬移数据
    				end-= gap;
    			}
    			array[end+gap] = k;
    		}
    		gap--;
    	}
    }

<table> 
 <thead> 
  <tr> 
   <th>应用场景</th> 
   <th>稳定性</th> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数据杂乱，数据量大</td> 
   <td>不稳定</td> 
   <td>与gap有关</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

### 选择排序 ###

*  选择排序

void SelectSort(int* array,int size)
    {
    	int i = 0;
    	for(i = 0;i<size-1;i++)
    	{
    		int j = 1;
    		int maxpos = 0;
    		for(;j<size-i;j++)
    		{
    			if(array[j]>array[maxpos])
    				maxpos = j;
    		}//找最大元素下标
    		if(maxpos != size-i-1)
    			Swap(&array[maxpos],&array[size-1-i]);//将最大元素放在区间最后
    	}
    }

优化  
同时排序最大元素和最小元素

void SelectSort_OP(int* array,int size)
    {
    	int begin = 0;
    	int end = size-1;
    	while(begin<end)
    	{
    		int minpos = begin;
    		int maxpos = begin;
    		
    		int i = begin+1;
    		//找最大及最小元素下标
    		while(i<=end)
    		{
    			if(array[i]>array[maxpos])
    				maxpos = i;
    			if(array[i]<array[minpos])
    				minpos = i;
    
    			++i;
    		}
    		if(maxpos != end)
    			Swap(&array[maxpos],&array[end]);
    		if(minpos == end)
    			minpos = maxpos;//最小元素有可能在end的位置，需要重新标记minpos
    		if(minpos!= begin)
    			Swap(&array[minpos],&array[begin]);
    		begin++;
    		end--;
    	}
    }

<table> 
 <thead> 
  <tr> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>应用场景</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>重复元素多</td> 
  </tr> 
 </tbody> 
</table>

*  堆排序

void HeapAdjust(int* array,int size,int parent)
    {
    	int child = (parent<<1)+1;//标记左孩子
    	while(child<size)
    	{
    		//找左右孩子中最大的
    		if(array[child] <array[child+1])
    			child+=1;
    		//检测最大孩子是否比双亲大
    		if(child +1<size&&array[child]>array[parent])
    		{
    			Swap(&array[child],&array[parent]);
    			parent = child;
    			child = (parent>>1)+1;
    		}
    		else 
    			return;
    	}
    }
    void HeapSort(int* array,int size)
    {
    	//1.建堆--升序：大堆
    	int end = size-1;
    	int root = ((end-1)>>1);
    	for(;root>=0;root--)
    	{
    		HeapAdjust(array,size,root);
    	}
    	//2.排序--删除
    	while(end>0)
    	{
    		Swap(&array[0],&array[end]);
    		HeapAdjust(array,end,0);
    		end--;
    	}
    }

<table> 
 <thead> 
  <tr> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

### 交换排序 ###

*  冒泡排序

void BubbleSort(int* array,int size)
    {
    	int i = 0;
    	int j =0;
    	for(i=0;i<size-1;i++)
    	{
    		int ischange = 0;
    		for(j = 0;j<size-i-1;j++)
    		{
    			if(array[j]>array[j+1])
    			{
    				ischange = 1;
    				Swap(&array[j],&array[j+1]);
    			}
    		}
    		if(!ischange)
    			return;
    	}
    }

*  快速排序  
    基本思想：递归  
    任取待排序序列中的某元素作为基准值，按照排序码将待排序序列分割为两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程即可。

void QuickSort(int* array,int left,int right)
    {
    	if(right-left > 1)
    	{
    		int boundary = Partion(array,left,right);
    		//[left，right）找基准值来划分区间，最后返回基准值在区间中的位置
    		QuickSort(array,left,boundary);
    		QuickSort(array,boundary,right);
    	}
    }

找基准值并划分左右区间的方法：

int Partion1(int *array,int left,int right)
    {
    	//找基准值
    	int key = array[right-1];//[left,right)
    	int begin = left;
    	int end = right-1;
    	while(begin<end)
    	{
    		//从左往右找比基准值大的元素
    		while(begin < end && array[begin]<= key)
    			begin++;
    		//从右往左找比基准值小的元素
    		while(begin < end && array[end]>=key)
    			end--;
    		if(begin<end)
    			Swap(&array[begin],&array[end]);
    	}
    	if(begin != right-1)
    		Swap(&array[begin],&array[right-1]);
    	return begin;
    }
    
    //填坑法
    int Partion2(int *array,int left,int right)
    {
    	int key = array[right-1];//[left,right)
    	int begin = left;
    	int end = right-1;
    
    	while(begin<end)
    	{
    		//从左往右找比基准值大的元素
    		while(begin < end && array[begin]<= key)
    			begin++;
    		if(begin<end)
    			array[end] = array[begin];
    		//从右往左找比基准值小的元素
    		while(begin < end && array[end]>= key)
    			end--;
    		if(begin<end)
    		{
    			array[begin] = array[end];
    			begin++;
    		}
    	}
    	array[begin] = key;
    	return begin；
    }
    
    
    int Partion3(int *array,int left,int right)
    {
    	int key = array[right-1];//[left,right)
    	int cur = left;
    	int prev = cur-1;
    	while(cur<right)
    	{
    		if(array[cur]<key && ++prev != cur)
    			Swap(&array[cur],&array[prev]);
    		++cur;
    	}
    	if(++prev != right-1)
    	{
    		Swap(&array[prev],&array[right-1]);
    	}
    	return prev;
    }

当代排序序列接近有序时，时间复杂度比较高，为了降低可以通过三数取中法：

int GetMiddleIndex(int* array,int left,int right)
    {
    	int mid = left+((right - left)>>1);
    	if(array[left]<array[right])
    	{
    		if(array[mid]<array[left])
    			return left;
    		else if(array[mid]>array[right-1])
    			return right-1;
    		else
    			return mid;
    	}
    	else
    	{
    		if(array[mid] > array[left])
    			return left;
    		else if(array[mid] < array[right-1])
    			return right-1;
    		else
    			return mid;
    	}
    }

<table> 
 <thead> 
  <tr> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>应用场景</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(n*log<sub>2</sub>n)</td> 
   <td>O（log<sub>2</sub>n）</td> 
   <td>数据越随机</td> 
  </tr> 
 </tbody> 
</table>

循环做法

void QuickSortNor(int* array,int size)
    {
    	int left = 0;
    	int right = size;
    	Stack s;
    	StackInit(&s);
    	StackPush(&s,size);
    	StackPush(&s,0);
    	while(!StackEmpty(&s))
    	{
    		left = StackTop(&s);
    		StackPop(&s);
    
    		right = StackTop(&s);
    		StackPop(&s);
    		if(left < right)
    		{
    			int boundary = Partion3(array,left,right);
    
    			//排左边--》将右半部分区间压栈
    			StackPush(&s,right);
    			StackPush(&s,boundary+1);
    			//排右边--》将左半部分区间压栈
    			StackPush(&s,boundary);
    			StackPush(&s,left);
    		}		
    	}
    }

### 归并排序 ###

void MergeData(int* array,int left,int mid,int right,int* tmp)
    {
    	int begin1 = left;
    	int end1 = mid;
    
    	int begin2 = mid;
    	int end2 = right;
    	int index = left;
    
    	while(begin1<end1 && begin2<end2)
    	{
    		if(array[begin1] <= array[begin2])
    			tmp[index++] = array[begin1++];
    		else
    			tmp[index++] = array[begin2++];
    	}
    	while(begin1 < end1)
    		tmp[index++] = array[begin1++];
    	while(begin2 < end2)
    		tmp[index++] = array[begin2++];
    }
    void _MergeSort(int* array, int left,int right,int* tmp)
    {
    	if(right-left>1)
    	{
    		int mid = left+((right-left)>>1);
    		_MergeSort(array,left,mid,tmp);
    		_MergeSort(array,mid,right,tmp);
    		MergeData(array,left,mid,right,tmp);
    		memcpy(array+left,tmp+left,(right-left)*sizeof(int));
    	}
    }
    
    void MergeSort(int* array,int size)
    {
    	int* tmp = (int*)malloc(sizeof(int)*size)
    	if(NULL == tmp)
    	{
    		assert(0);
    		return;
    	}
    	_MergeSort(array,0,size,tmp);
    
    	free(tmp);
    }