标签：分析   结构   lis   private   current   相等   down   数据结构   检测   

排序码(key):排序的关键字。

排序的稳定性：若相等的两个元素经过排序后顺序仍不变则称排序算法是稳定的。

一个b站学习视频

一、快速排序

（一）原理
选择一个元素作为基准元素，将小于基准元素的都放在其左边，将大于基准元素的都放在其右边。这样序列就被划分为大于和小于基准元素的两部分。对这两部分分别递归处理。基准元素随意选。
（二）代码

//快速排序---我自己的板子
#include
#include
#define N 100009
using namespace std;

int n;
int a[N];

void qsort(int l,int r)
{
	int mid=a[(l+r)>>1];
	int i=l,j=r;
	do{
		while(a[i]mid) j--;
		if(i

//课本上的代码...考试用
#include"dataList.h"
template
void QuickSort(dataList&L,const int left,const int right)
{
	if(left
int dataList::Partition(const int low,const int high)
{
	int pivotpos=low;Elementpivot=Vector[low];
	for(int i=low+1;i

(三)时间复杂度分析
O(nlogn)

二、堆排序

（一）原理：小根堆保证父亲小于两个儿子，大根堆保证父亲大于两个儿子。
（二)代码

//堆排 
#include
#include
#define N 1000009
using namespace std;

int n,tot;
int d[N];

void up(int x)
{
	if(x==0) return;
	if(d[x]tot) return;
	if(x*2+1>tot) nxt=x*2;
	else nxt=d[x*2]d[nxt])
	{
		swap(d[x],d[nxt]);
		down(nxt);
	}
}
 
int main()
{
	scanf("%d",&n);
	for(int i=1;i

#define DefaultSize 10;
template
struct Element
{
	T key;
	field otherdata;
	Element& operator = (Element&x)
	{
		key=x.key;
		otherdata=x.otherdata;
	}
	bool operator >= (Element&x){return key>=x.key;}
	bool operator &x){return key
class MaxHeap{
	public:
		MaxHeap(int sz=DefaultSize);//构造函数，建立空堆
		MaxHeap(Elementarr[],int n);//构造函数
		~Maxheap(delete []heap;)//析构函数
		bool Insert(Element&x);//将x插入到最大堆中
		bool Remove(Element&x);//删除堆顶上的最大元素
		bool IsEmpty() const{return currentSize==0;}
		bool IsFull() const{return currentSize==maxHeapSize;}
	private:
		Element*heap;
		int currentSize;
		int maxHeapSize;
		void siftDown(int start,int m);//从start到m自顶向下调整
		void siftUp(int start);         //从start到0自底向上调整
		Swap(const int i,const int j)
		{
			Elementtmp=heap[i];
			heap[i]=heap[j];
			heap[j]=tmp;
	    }
};

template
void maxHeap::siftDown(const int start,const int m)
{
	int i=start;int j=2*i+1;
	Elementtemp=heap[i];//暂存子树根节点
	while(j=heap[j]) break;
		else{
			heap[i]=heap[j];
			i=j;j=2*j+1;
		} 
	} 
	heap[i]=temp;
};
#include"maxheap.h"
template
void HeapSort(maxHeap&H)
{
	for(int i=(currentSize-2)/2;i>=0;i--) siftDown(i,currentSize-1);
	//将表转换成堆
	for(int i=currentSize-1;i>=0;i--)
	{
		Swap(0,i);siftDown(0,i-1);
	} 
};

（三）时间复杂度
O(nlogn)

三、希尔排序

（一）原理：将数组下标相差gap的元素进行插入排序，然后不断缩小gap。
（二）代码

#include
#include
#include
#define N 100009
using namespace std;

int n;
int a[N]; 

void ShellSort()
{
	int j,temp,d;
	d=n/2;
	while(d>0)
	{
		for(int i=d+1;i0&&a[j]>temp)
			{
				a[j+d]=a[j];
				j=j-d;
			}
			a[j+d]=temp;
		}
		d/=2;
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i

#include"dataList.h"
template
void Shellsort(dataList&L,const int left,const int right)
{
	int i,j,gap=right-left+1;
	Elementtemp;
	do{
		gap=gap/3+1;
		for(i=left+gap;i=left&&temp1);
};

(三)时间复杂度
O(n^(1.3—2))

四、插入排序

（一）每一个元素与其前面已经有序的元素比较，插入到合适的位置。
（二）代码
(1)直接插入排序

#include"dataList.h"
template
void InsertSort(dataList&L,const int left,const int right)
{
	Elementtemp;int i,j;
	for(int i=left+1;i=left&&temp

#include
#include
#include
#include
#define N 1000009
using namespace std;

int n;
int a[N];

void InsertSort(int a[],int left,int right)
{
	int temp,j; 
	for(int i=left+1;itemp);
			a[j+1]=temp;
		}	  
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i

(2)折半插入排序

#include"dataList.h"
template
void BinaryInsertSort(dataList&L,const int left,const int right)
{
	Elementtemp;int i,low,high,middle,k;
	for(int i=left+1;i=low;k--) L[k+1]=L[k];  //[low,i-1]后移 
		L[low]=temp;                    //low就是插入的位置 
	}
} 

#include
#include
#include
#define N 100009
using namespace std;

int n;
int a[N];

void BinaryInsertSort(int a[],int left,int right)
{
	int i,low,high,middle,k,temp;
	for(int i=left+1;itemp)
			{
				high=middle-1;
			}else low=middle+1;
		}
		for(k=i-1;k>=low;k--) a[k+1]=a[k];
		a[low]=temp;
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i

(三)时间复杂度
(1)直接插入 O(n^2)
(2)折半插入 O(n^2)

五、归并排序

（一）原理：递归减少区间大小，然后再合并。
（二）代码

//归并排序 
#include
#include
#include
using namespace std;

int n,a[100009],tmp[100009];

void merge_sort(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int ii=l,jj=mid+1,k=l;
    while(ii

#include"dataList.h"
template
void merge(dataList&L1,dataList&L2,const int left,const int mid,const int right)
{
	for(int k=left;k&L,dataList&L2,int left,int right)
{
	if(left>=right) return;
	int mid=(left+right)/2;
	mergeSort(L,L2,left,mid);
	mergeSort(L,L2,mid+1,right);
	merge(L,L2,left,mid,right); 
}

(三)时间复杂度
O(n log n)

六、选择排序

(一)原理： 每次选择没被选择元素中最小的放到已经排序的序列里。
(二)代码

//选择排序 
#include"dataList.h"
template
void SelectSort(dataList&L,const int left,const int right)
{
	for(int i=left;i

#include
#include
#define N 1000009
using namespace std;

int n,a[N];

int main()
{
	scanf("%d",&n);
	for(int i=1;i

(三)时间复杂度
O(n^2)

七、冒泡排序

（一）原理：相邻元素不停交换，每次都会有一个最小的被挤到序列的一端。
（二）代码

//冒泡排序 
#include
#include
#define N 100009
using namespace std;

int n;
int a[N];

int main()
{
	scanf("%d",&n);
	for(int i=1;ia[j+1]) swap(a[j],a[j+1]);
		}
	}
	for(int i=1;i

(三)时间复杂度
O(n^2)

第一次用markdown....
整理太费时间了...不考的我下次不整了...

【数据结构】排序

标签：分析   结构   lis   private   current   相等   down   数据结构   检测   

原文地址：https://www.cnblogs.com/zzyh/p/13178986.html