数据结构——交换排序（冒泡排序和快速排序。）

交换排序

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

//冒泡排序

#include<stdio.h>

void bubble_sort( int a[],int n)
{
    int m,j,flag=1;
    int temp;
    for(m=1;m<n&&flag==1;m++)
    {   
	    flag=0; 
    	for(j=1;j<=n-m;j++)
    	{
    		if(a[j+1]<a[j])
    		{
    			flag=1;
    			temp = a[j];
    			a[j]=a[j+1];
    			a[j+1]=temp;
			 } 
		}
	}

 } 
 int main()
{
	int i;
	int a[9];
	for( i =1;i<=8;i++)
	{
		a[i]=8-i;
	}
	for(i = 1;i<=8;i++)
	{
		printf("a[%d]=%d\n",i,a[i]);
	}
	bubble_sort(a,9);
	for(i=1;i<=8;i++)
	{
		printf("a[%d]=%d\n",i,a[i]);
	}
	return 0;
	
	 
 }

在这里插入图片描述

快速排序

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

#include<stdio.h>



int Partition(int a[],int low, int high) 

{
	a[0]=a[low];
	while(low<high)
	{
		while(low<high&& a[0]<=a[high]) high--;
		a[low]=a[high];
		while(low<high && a[low]<=a[0])low++;
		a[high]=a[low]; 
	}
	a[low]=a[0];
	return low;
	
}
void Qsort( int a[],int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc = Partition(a,low,high);
		Qsort(a,low,pivotloc-1);
		Qsort(a,pivotloc+1,high);
	}
}


 int main()
{
	int i;
	int low=1,high=8;
	int a[9]={0,49,38,65,97,76,12,27,49};
	for(i = 1;i<=8;i++)
	{
		printf("a[%d]=%d\n",i,a[i]);
	}
	Qsort(a,low,high);
	for(i=1;i<=8;i++)
	{
		printf("a[%d]=%d\n",i,a[i]);
	}
	return 0;
	
	 
 }