L3数据结构-排序（day13）一、排序的原理二、快速排序的实现 d13作业：

90 阅读 0 评论 60 点赞

我是靠谱客的博主炙热电话，最近开发中收集的这篇文章主要介绍L3数据结构-排序（day13）一、排序的原理二、快速排序的实现 d13作业：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、排序的原理

一、排序的定义

插入排序：

交换排序：

二、快速排序的实现

d13作业：

一、排序的原理

一、排序的定义

稳定排序和非稳定排序
设文件f=（R1……Ri……Rj……Rn）中记录Ri、Rj（i≠j，i、j=1……n）的key相等，即Ki=Kj。
若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。
内排序和外排序
若待排文件f在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。
若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。

各种内排序方法可归纳为以下五类：
（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
......

插入排序：

直接插入排序折半插入排序链表插入排序 Shell（希尔）排序 ……

直接插入排序：设待排文件f=（R1 R2……Rn）相应的key集合为k={k1 k2……kn}，
排序方法
先将文件中的（R1）看成只含一个记录的有序子文件，然后从R2起，逐个将R2至Rn按key插入到当前有序子文件中，最后得到一个有序的文件。插入的过程上是一个key的比较过程，即每插入一个记录时，将其key与当前有序子表中的key进行比较，找到待插入记录的位置后，将其插入即可。

折半插入排序：排序算法的T(n)=O(n2),是内排序时耗最高的时间复杂度。

折半插入排序方法
先将（R[1]）看成一个子文件，然后依次插入R[2]……R[n]。但在插入R[i]时，子表[R[1]……R[i-1]]已是有序的，查找R[i]在子表中的位置可按折半查找方法进行，从而降低key的比较次数。

链表插入排序：设待排序文件f=（R1 R2……Rn），对应的存储结构为单链表结构

链表插入排序实际上是一个对链表遍历的过程。先将表置为空表，然后依次扫描链表中每个结点，设其指针为p，搜索到p结点在当前子表的适当位置，将其插入。

见day6作业

交换排序：

1、冒泡排序：设记录key集合k={50，36，66，76，95，12，25，36}，排序过程如下：

2、快速排序：设记录的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一个key为基准的快速排序过程如下：

二、快速排序的实现

代码：

sort.c:

#include <stdio.h>
#include <stdlib.h>//srandom函数需要的头文件

#define N 15

int partion(int *data, int low, int high);
int quick_sort(int *data, int low, int high);
int compare(const void *p1, const void *p2);

int main(int argc, const char *argv[])
{
	int data[N] = {0};
	int i;

	srandom(10);//设置一个种子才能得到随机值

	for (i = 0; i < N; i++) {
		data[i] = random() % 100;//random返回的值可能比较大，所以对100取余
	}

	for (i = 0; i < N; i++) {
		printf("%d ", data[i]);
	}
	puts("");

	//quick_sort(data, 0, N-1);//起点就是下标0，终点是N-1
	qsort(data, N, sizeof(int), compare);//qsort函数就是快排（待排数组，元素个数，每一个元素大小，比较函数）

	for (i = 0; i < N; i++) {
		printf("%d ", data[i]);
	}
	puts("");

	return 0;
}

//第一次排序，找中轴
int partion(int *data, int low, int high) {
	int temp = data[low];//用temp来存储基准点，第一个基准点默认就是low，最左边的值

	while (low < high) {//low和high重合的时候循环结束
		while (low < high && temp <= data[high]) {//low<high这个条件是因为如果默认基准点是最小的值，high--，比较到最后high和自己重合了
			high--;
		}
		data[low] = data[high];//碰到了high位置的值比基准点小，所以把high的值放过来

		while (low < high && temp >= data[low]){//上一步放过来之后，现在从左边开始比
			low++;
		}
		data[high] = data[low];
	}

	data[low] = temp;//找到一个中轴

	return low;
}

int quick_sort(int *data, int low, int high) {
	int t;//记录中轴的位置

	if (data == NULL) {
		return -1;
	}

	if (low >= high)//出口
		return 0;

	t = partion(data, low, high);//找到一个中轴
	quick_sort(data, low, t-1);//左半部分继续
	quick_sort(data, t+1, high);//右半部分继续，这是一个递归的过程

	return 0;
}

int compare(const void *p1, const void *p2) {//返回值int，两个参数const_void*
	return (*(const int *)p1 - *(const int *)p2);//先换成int指针
	                                              // 第一个元素指待比较第一个元素的地址
}

运行结果：

d13作业：

1、利用快速排序对以下数据进行排序1,5,7,8,3,5,9,4,1,0

代码：2.c

#include <stdio.h>
int a[20],n;
void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
       return;
    temp=a[left]; //temp用来保存基准数
    i=left;
    j=right;
    while(i!=j)
    {
       //从右边开始找
       while(a[j]>=temp && i<j)
            j--;
       //再找右边的
       while(a[i]<=temp && i<j)
            i++;
       //交换两个数在数组中的位置
       if(i<j)
       {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
       }
    }
    //将基准数归位
    a[left]=a[i];
    a[i]=temp;

    quicksort(left,i-1);//继续处理左边的
    quicksort(i+1,right);//处理右边的
}
int main()
{
    int i,j,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quicksort(1,n); 

    for(i=1;i<=n;i++)
        printf("%d ",a[i]);
    getchar();
    getchar();
    return 0;
}

运行结果：