学步园

常用的排序算法有冒泡排序，选择排序，插入排序，归并排序、希尔排序，堆排序等

1、冒泡

冒泡排序就是像旗袍一样，最大的值逐渐上浮，我的实现方法是采用递归的，当然也可以不用递归

void bubbleSort2(int array[],int length)
{
	if(length==1)
		return;
	int index=0;
	for(int i=0;i<length;i++)
	{
		if(array[i]>array[index])
			index=i;
	}
	if(index!=length-1)
	{
		int temp=array[index];
		array[index]=array[length-1];
		array[length-1]=temp;
	}

	bubbleSort2(array,length-1);

}

2，插入排序：插入排序将整个序列分成两个部分，有序区和无序区，我们要做的工作就是依次地把无序区的值插入到有序区中去

当然首先先从第一个元素开始，假设第一个元素是有序区

void InsertSort(int array[],int length)
{
	int index=0;
	for(int i=1;i<length;i++)
	{
		int temp=array[i];
		int j=i-1;
		while(j>=0 && array[j]>temp){
			array[j+1]=array[j];
			j--;
		}
		array[j+1]=temp;

	}

}

3、选择排序

选择排序的思想是选取无序区的最大值放在有序区的末尾

void selectionSort(int array[],int length)
{
	int index=0;
	while(index<length){
		int min=index;
		for(int i=index+1;i<length;i++)
		{
			if(array[i]<array[min])
			{
				min=i;
			}
		}
		if(min!=index)
		{
			int temp=array[min];
			array[min]=array[index];
			array[index]=temp;
		}

		index++;
	}
}

4，shell排序

shell排序的基本思想是给出一个增量gap，每个元素只跟他距离gap的元素比较，这样就可以一次跳过多个元素进行比价

void shellSort2(int array[],int length)
{
     int gap=length/2;
     while(gap>0)
     {
         for(int i=gap;i<length;i++)
         {
                 int temp=array[i];
                 int j=i-gap;
                 while(j>=0 && array[j]>temp)
                 {
                      array[j+gap]=array[j];
                      j-=gap;
                 }
                 array[j+gap]=temp;
         }
         gap/=2;
     }
}

5，归并排序，归并排序就是对两个已经排好序的序列合并排序，以数组为例，首先把数组分成左右两个已经排好序的数组，会后进行归并

//merge作为mergesort的辅助函数
void merge(int a[], int p, int q, int r)//p-r是一个序列，r到q是一个序列
{
	int n1=r-p+1, n2=q-r;
	//int L[n1],R[n2];
	int* L = new int[n1];
	int* R = new int[n2];
	//下面两个for循环是分成左右两个数组，然后归并
	for(int i=0;i<n1;i++)
	{
		L[i] = a[p+i];
	}

	for(int j=0;j<n2;j++)
	{
		R[j] = a[r+j+1];
	}

	int i=0,j=0;
	for(int k=p; k<=q;k++)
	{
		//下面就是交换的过程
		if(i<n1 && j<n2)
		{
			if(L[i]<R[j])
			{
				a[k] = L[i];
				i++;
			}
			else
			{
				a[k] = R[j];
				j++;
			}
		}
		else if(i<n1)
		{
			a[k] = L[i];
			i++;
		}
		else
		{
			a[k] = R[j];
			j++;
		}
	}
}


void mergeSort(int a[],int start, int end)
{
	if(start < end)
	{
		int r=(end + start)/2;
		mergeSort(a, start, r);
		mergeSort(a, r+1, end);
		merge(a,start, end, r);
	}
}