插入、希尔、选择、堆、冒泡、快速、归并排序实现:数据结构与算法分析

基于比较、渐进最优、最好情况只能降到O(nlogn):

Insert sort 插入排序 O(N^2) 稳定

void Insert_sort(int a[],int n) //插入排序
{
int i,j,temp;
for(i=1;i<n;i++)//把起始点看作是排好的序列,从第2个点开始向该序列插入
{
	temp=a[i];//把待插入的点保存
	for(j=i-1;temp<a[j]&&j>=0;j--)//将待插入点与已排好的序列的尾部开始比较 
//稳定的插入排序,不使用<=而是用<
{
		a[j+1]=a[j];
}//循环执行完还有一个减一	
	a[j+1]=temp;
}
}

Shell sort希尔排序 O(N)~O(N^2)平均O(N^1.5) 不稳定

Void Shell_sort(int a[],int n)   //希尔排序
{
	int i,j,k,temp;
    for(k=(n/2);k>=1;k=k/2)    //间隔从n/2 到1 
{
		for(i=k;i<n;i++)  //一定间隔下对各组进行插入排序,从已排好序列尾部出发
		{
		 temp=a[i];
		 for(j=i-k;temp<a[j]&&j>=0;j=j-k) //将待插入点与已排好的序列的尾部开始比较
{
			 	a[j+k]=a[j];
			}		
			 a[j+k]=temp;
		}
	}
}

Select sort选择排序 O(N^2) 不稳定

void Select_sort(int a[],int n)  
{
	int i,j,k,temp;
    for(i=0;i<n-1;i++)
	{
		k=i;       ///将a[0]作为初始元素
		for(j=i+1;j<n;j++)  //从第2到第n-1中找最小的
		 if(a[j]<a[k])
		 k=j;       k存放后面标号最小的
		 if(k!=i)     //若找到的最小元素比a[i]小,二者交换
		 {
			 temp=a[k];
			 a[k]=a[i];
			 a[i]=temp;
		 }
	}
}

Heap sort 堆排序 O(N*logN) 不稳定

方式一:
void heap_adjust( int R[], int low, int high)
{
  int i=low, j=2*I;   //R[j]是R[i]的左孩子
  int temp=R[i];
  while(j<=high)
{
   if(j<high&&R[j]<R[j+1])
   j++;             -----j的位置放的是值大的孩子
 if(temp<R[j]) { R[i]=R[j]; ---将R[j]调整到双亲的位置 i=j; j=2*i; } else break; ----双亲大,不需调整 } R[i]=temp; } void heap_sort( int R[], int n) { int i; int temp; for(i=n/2;i>=1;i--) ---循环建立初始堆
    heap_adjust(R,i,n);
  for(i=n;i>=2;i--)
  {  
     temp=R[1];
     R[1]=R[i]
     R[i]=temp;
     heap_adjust(R,1,i-1);    ---调整R[1]
   }
}
方式二:
template
void adjust(T* arr,int sign,int len){
    T temp = arr[sign];
    //每一次循环都更新该父节点为根的完全二叉树最大堆
    for (int i = sign * 2 + 1; i < len; i = i * 2 + 1){
    //不断往下深入,比较两个子节点
        if (i + 1 < len && arr[i + 1] > arr[i])
            i++;
        //判断较大的子节点 大于父节点 
        if (arr[i] > temp){
            arr[sign] = arr[i];
            sign = i;
        }
    }
    arr[sign] = temp;
}
template
void sort(T* arr,int length){
    //1.从所有非叶子节点 构建初始大顶堆
    for (int i = length / 2 - 1; i >= 0; i--){
    自下而上的下滤
        adjust(arr, i, length);
    }
    //
    for (int i = length - 1; i; i--){
        //2.交换最大堆 和 相对的最后一个元素
        swap(arr, i, 0);
        //3.重新调整堆结构
        adjust(arr, 0, i);
    }
}

Bubble sort冒泡排序 O(N^2) 稳定

void bubble_sort(int a[],int n) 
{
 int i,j,temp;
  for(i=1;i<n;i++)  //做n-1次循环,每次交换的次数递减
	 for(j=0;j<n-i;j++) //第1次做n-1次交换,第2次做n-2次交换...,第n-1次做1次交换 //每次末尾都会增加一个选取的最大元素,不用参与下次排序 if(a[j]>a[j+1])
		 {
			 temp=a[j];
			 a[j]=a[j+1];
			 a[j+1]=temp;
		 }
}

Quick sort 快速排序 O(N*logN)-O(N^2) 平均为O(N*logN) 基点用头中尾三点中间的一个 不稳定

void quick_sort(int arr[], int left, int right) 
{
    if (left > right)
        return;
    int j = partition(arr, left, right);//按照j划分
    quick_sort(arr, left, j - 1);
    quick_sort(arr, j + 1, right);
}
方式一:
void partition(a[],int low,int high)
{
  int temp;
  temp=a[low];
  while(low<high)
{
      while(low<high&&a[high]>=temp)
      high=high-1;
      if(low<high)
      {
         a[low]=a[high];
         low=low+1;
      }
      while(low<high&&a[low]<=temp)
      low=low+1;
     if(low<high)
{
    a[high]=a[low];
    high=high-1;
}
}
a[low]=temp;
return low;
}
方式二:
int partition(int arr[], int left, int right)  //找基点,划分
{
    int i = left + 1 ;
    int j = right;
    int temp = arr[left];//以最左边为基准
    while(i <= j)
    {
        while (arr[i] < temp) i++; while (arr[j] > temp )
            j--;
        if (i < j)
            swap(arr[i++], arr[j--]);
        else i++;
    }
    swap(arr[j], arr[left]);//把左点基准放到中间位置
    return j;
}

Merge sort 归并排序 O(N*logN) 稳定

方式一:
int *temp = new int[n];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
调用方法:merge_sort (arr,0,n-1,temp);
void merge_sort(int arr[],int left,int right,int temp[])
{//分是用递归完成的
        if(left<right)
{
            int mid = (left+right)/2;
            merge_sort (arr,left,mid,temp);//左边归并排序,使得左子序列有序
            merge_sort (arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
           }
    }
void merge(int arr[],int left,int mid,int right,int temp[])
{
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right)
{
            if(arr[i]<=arr[j])
{
                temp[t] = arr[i]; t++;i++;
             }
else
 			{
                temp[t] = arr[j]; t++;j++;
            }
         }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t] = arr[i]; t++;i++;
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t] = arr[j];  t++;j++;
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right)
{
            arr[left] = temp[t]; left++;t++;
          }
  }
方式二(vector向量):
void merge(vector&arr, int start, int mid, int end)
{//左右部分归并
	vector tmp;//辅助数组
	int i = start;
	int j = mid+1;
	while (i <= mid&&j <= end)
	{
		if (arr[i] <= arr[j])
			tmp.push_back(arr[i++]);
		else
			tmp.push_back(arr[j++]);
	}//左边和右边肯定有一边到头了,不可能同时,因为每次只移动一边
	while(i <= mid)
		tmp.push_back(arr[i++]);
	while (j <= end)
		tmp.push_back(arr[j++]);
	//将排好序的辅助数组赋值给原始数组
	for (int i = 0; i < tmp.size(); i++)
		arr[start + i] = tmp[i];
}
void mergeSort(vector&arr, int start, int end)
{
	if (arr.empty()||start >= end)
		return;
	//将数组一分为二
	int mid = (end + start) / 2;
	先将左半部分排好序,再将右半部分排好序
	mergeSort(arr, start, mid);
	mergeSort(arr, mid+1, end);
	//左右部分归并
	merge(arr, start, mid, end);
	for (int i = 0; i < arr.size(); i++)
		cout << arr[i]<<" ";
}

相关内容:
数据结构复习笔记与一些总结:https://www.svip.tech/archives/907
基于比较、渐进最优的排序算法(插入、希尔、选择、堆、冒泡、快速、归并排序实现):https://www.svip.tech/archives/1152
不基于比较、线性时间运行的排序算法(计数、基数、桶排序分析)和顺序、对分查找实现:https://www.svip.tech/archives/1165
各种算法特性与复杂度总结:https://www.svip.tech/archives/1174

发表评论

电子邮件地址不会被公开。 必填项已用*标注