排序(Sort)

排序(Sort)是将无序的记录序列（或称文件）调整成有序的序列。

排序的目的是方便我们队数据查询记录、修改记录等操作。

 

排序的分类

按稳定性可分为稳定排序和非稳定排序，按待排序数据的存储位置又可分为内排序和外排序。


截止目前，各种内排序方法可归纳为以下五类：
（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
（5）基数排序。

本次介绍的是简单常用的快速排序算法，直接快速排序属于交换排序算法！

 

快速排序

经过key的一趟比较后，确定某个记录在排序后的最终位置。

 

算法思路

一趟排序的过程：选择一个基准，将右端元素中所有比基准小的数值交换到左边，然后将左边所有比基准大的数值放到右边。经过反复比较、交换，最终确定基准的位置。

递归调用实现排序：将原序列分成左右两个部分。再对每个子序列进行同样的操作，最终排序完毕。

递归过程：在递归实现中，分别有两次对自身进行调用。先对左子序列进行递推操作（确定左子序列的基准位置）直到达到回归条件，在第一个quicksort函数回归的过程中，同时也是第二个quicksort函数递推（确定右子序列的基准的位置）的过程，直到整个递归过程结束，也就排完序了。

//一趟快速排序
int quickpass(int a[],int i,int j)
{
      int tmp;
      tmp = a[i];   //将a[i]作为基准保存
      while(i < j){
	    //从上界比较
	    while(i < j && tmp <= a[j])
		  j--;
	    //将a[j]交换到左边
	    if(i < j)
		  a[i] =a[j];
	    //从下界比较
	    while(i < j && tmp >= a[i])
		  i++;
	    //将a[i]交换到右边
	    if(i < j)
		  a[j] = a[i];
      }
      a[i] = tmp;   //将基准放到最终的位置
      return i;	  //返回基准的下标
}

void quicksort(int a[],int low,int high)
{
      int mid;
      if(low < high){
	    mid = quickpass(a,low,high);   //一趟快速排序 
	    show(a);
	    quicksort(a,low,mid-1);   //基准左边序列进行快速排序
	    quicksort(a,mid+1,high);   //基准右边序列进行快速排序
      }
}

 

过程分析