掌握C语言：如何实现数据按字段排序的技巧

一、掌握C语言：如何实现数据按字段排序的技巧

在软件开发中，数据排序是一项常见且重要的功能，尤其是在处理大量数据时。在C语言中，按照字段对数据进行排序不仅能使数据更易于理解，还能提升程序的性能和用户体验。本文将深入探讨在C语言中如何实现数据按字段排序的方法，包括常用的排序算法，以及如何在实际应用中选择合适的算法。

什么是数据排序？

数据排序是指根据某种特定规则将数据元素重新排列的过程。在计算机科学中，排序通常按照升序或降序的方式进行。字段排序特指根据数据结构中的特定字段对数据进行排序。比如，对于包含多个属性的数据结构，可以选择某个属性作为排序依据。

为什么需要字段排序？

字段排序在许多场景中都是必不可少的，以下是几种常见的应用：

• 提高可读性：经过排序的数据更易于查看和理解。
• 快速检索：排序的数据能提高搜索效率，特别是在需要进行二分查找的情况下。
• 数据分析：通过排序可以更方便地进行统计分析和模式识别。

C语言中的排序算法

C语言中有多种排序算法，以下是一些常用的排序算法及其简要介绍：

• 冒泡排序（Bubble Sort）：通过重复遍历需要排序的数据，逐一比较相邻元素并交换位置，将最大的元素“冒泡”至顶端。适合用于小规模数据的排序。
• 选择排序（Selection Sort）：每次找到当前未排序部分中的最小（或最大）元素，将其放到已排序部分的末尾。执行效率不高，但实现简单。
• 插入排序（Insertion Sort）：通过构建一个有序序列，将新元素插入到已排序部分的合适位置。适合用于部分已排序的数据。
• 快速排序（Quick Sort）：采用分治法，通过选择基准元素将数据分成两部分，使左边的元素都小于基准元素，右边的元素都大于基准元素，递归排序两部分。效率较高。
• 归并排序（Merge Sort）：也是一种分治法，将数据分为两部分分别排序，再将已排序的部分合并。适合大规模数据排序。

在C语言中按字段排序的实现方法

为了在C语言中实现数据的字段排序，首先需要定义一个数据结构，接着通过指针和函数对数据进行排序。以下是一个简单的例子，展示如何按名字的字母顺序对学生信息进行排序。

#include <stdio.h>
#include <string.h>

typedef struct {
    char name[50];
    int age;
} Student;

void swap(Student *xp, Student *yp) {
    Student temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void bubbleSort(Student arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (strcmp(arr[j].name, arr[j+1].name) > 0) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

void printArray(Student arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%s, %d\n", arr[i].name, arr[i].age);
}

int main() {
    Student students[] = {{"Alice", 23}, {"Bob", 22}, {"Charlie", 21}};
    
    int n = sizeof(students) / sizeof(students[0]);
    bubbleSort(students, n);
    
    printf("Sorted students by name:\n");
    printArray(students, n);
    return 0;
}
  

在上述例子中，我们定义了一个Student结构体，包含了姓名和年龄两个字段。随后，利用bubbleSort函数对学生信息按照姓名进行排序。这个例子展示了如何通过简单的冒泡排序算法进行按字段排序。

选择合适的排序算法

在选择排序算法时，需要考虑以下几点：

• 数据规模：小规模数据可以选择简单易实现的算法，如冒泡排序和选择排序；大规模数据则更适合快速排序或者归并排序。
• 数据分布：对于部分已排序的数据，插入排序具有较高的效率，而对于完全随机的数据，快速排序和归并排序表现更优。
• 空间复杂度：有些排序算法需要额外的内存空间，如归并排序，而有些算法则是原地排序，如快速排序。

总结

在本文中，我们深入探讨了如何在C语言中实现数据按字段排序的技巧，从基本的排序算法到具体的实现方法。希望通过此篇文章，可以帮助开发者们更好地理解用C语言进行数据排序的原理和实现，这将极大地提升您的软件开发技能。

感谢您耐心阅读这篇文章，希望本文对您有所帮助，以便您在实际工作中更加灵活地运用数据排序的技巧，实现更高效的程序开发。

二、c语言数据类型精度排序？

double float long int shortint 应该就是这样

三、c语言数据类型等级排序？

第一、冒泡排序（Bubble Sort）

排序原理：重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

二、选择排序（Selection sort）

工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

三、插入排序（Insertion Sort）

工作原理：是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

四、归并排序（简单）

工作原理：归并排序要稍微复杂一点，归并排序的实现分为 递归实现 与 迭代实现 。

递归实现的归并排序是算法设计中分治算法（算法后期再说）的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。

非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并成倍，一直类推直到归并了整个数组。

五、快速排序

工作原理：

在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

四、C语言链表中如何实现对一组数据进行排序？

#include<stdio.h>

#include<stdlib.h>

#define NULL 0

struct student * creat();

struct student * link(struct student * head_a,struct student * head_b);

void print(struct student * head);

struct student{

int num;

float score[2];

struct student *next;

}stu;

int main(void)

{

struct student *head_a;

struct student *head_b,*head_c;

printf("请输入a链表学生的数据：0 0 0结束输入\n");

head_a=creat();

print(head_a);

printf("请输入b链表学生的数据：0 0 0结束输入\n");

head_b=creat();

print(head_b);

head_c=link(head_a,head_b);

printf("打印经过排序之后的学生数据,a,b链数据的结合\n");

print(head_c);

return 0;

}

struct student * creat()

{

int n=0;

struct student * head,*p1,*p2;

p1=p2=(struct student *)malloc(sizeof(struct student ));

scanf("%d%f%f",&p1->num,&p1->score[0],&p1->score[1]);

head=NULL;

while(p1->num!=0)

{

n=n+1;

if(n==1) head=p1;

else p2->next=p1;

p2=p1;

p1=(struct student *)malloc(sizeof(struct student));

scanf("%d%f%f",&p1->num,&p1->score[0],&p1->score[1]);

}

p2->next=NULL;

return head;

}

void print(struct student * head)

{

struct student *p;

p=head;

while(p!=NULL)

{

printf("%-10d%-10.1f%-10.1f\n",p->num,p->score[0],p->score[1]);

p=p->next;

}

return ;

}

struct student * link(struct student * head_a,struct student * head_b)

{

int n,m;

m=n=0;

struct student * head,*p1,*p2,*p3,*q;//q是在冒泡排序是（共需N-1趟排序）每趟的最后一次指针p1的位置，开始时q为Null

p1=head_a;

p2=head_b;

head=head_a;

while(p1->next!=NULL)

{p1=p1->next;n++;}

p1->next=p2;

p1=head_a;

while(p1!=NULL)

{

p1=p1->next;

n++; //n是计算链表的节点数，以备后面的排序用

}

q=NULL;

p1=head_a;

p2=p1->next ;

while(m<n)

{

m++;

//以下是采用冒泡法进行排序

while(p2!=q)

{

if(p1->num>p2->num)

{

if(head==p1) head=p2;

else p3->next=p2;

p1->next=p2->next;p2->next=p1;

//以下是按照 p3 p1 p2排序

p3=p2;p2=p1->next;

}

else

{

p3=p1;p1=p1->next;p2=p2->next;

}

}

q=p1;p1=head;p2=p1->next;

}

return (head);

}

五、C语言--怎样实现输入任意几个数排序？

楼主的思路是对的。不能直接对数组用动态定义，但是可以对指针使用。所以动态定义一个指针，把它当成数组用。我把你的程序做了些简单的修改，运行成功。

源程序如下：

#include

#include

main()

{

float *a;

int i,j,length;

printf("请输入要排序数字的个数:\n");

scanf("%d",&length);

a=(float *)malloc(length*sizeof(float));

printf("请输入%d个数(数字之间用空格或回车隔开):\n",length);

for(i=0;i

六、c语言实现冒泡排序法是否可以实现float型数组的排序？

用冒泡排序法排序float数组没有任何问题

七、c语言如何实现从网络读取数据？

在C语言中，可以使用`sockets`库实现从网络读取数据。`sockets`库是一个用于处理网络通信的编程接口，提供了创建套接字、发送和接收数据的功能。下面是一个简单的示例，展示如何使用C语言从网络读取数据：

1. 首先，需要包含`sys/socket.h`头文件，用于处理套接字相关操作。

```c

#include <sys/socket.h>

#include <arpa/inet.h>

#include <stdio.h>

#include <unistd.h>

#include <string.h>

#include <errno.h>

```

2. 定义一个函数`get_sockaddr_port`，用于创建套接字地址结构。

```c

struct sockaddr_in *get_sockaddr_port(char *host, int port) {

    struct sockaddr_in *sock_addr = (struct sockaddr_in *) malloc(sizeof(struct sockaddr_in));

    sock_addr->sin_family = AF_INET;

    sock_addr->sin_port = htons(port);

    if (inet_pton(AF_INET, host, &sock_addr->sin_addr) <= 0) {

        printf("inet_pton error for %s\n", host);

        free(sock_addr);

        return NULL;

    }

    return sock_addr;

}

```

3. 定义一个函数`get_data`，用于从套接字读取数据。

```c

char *get_data(int sock_fd) {

    char buffer[1024];

    ssize_t len = read(sock_fd, buffer, sizeof(buffer) - 1);

    if (len < 0) {

        printf("read error: %s\n", strerror(errno));

        return NULL;

    }

    buffer[len] = '\0';

    printf("Received data: %s\n", buffer);

    return buffer;

}

```

4. 编写主函数，创建套接字、连接服务器、读取数据并关闭套接字。

```c

int main() {

    int sock_fd;

    struct sockaddr_in *sock_addr;

    // 创建套接字

    sock_fd = socket(AF_INET, SOCK_STREAM, 0);

    if (sock_fd < 0) {

        printf("socket error: %s\n", strerror(errno));

        return -1;

    }

    // 连接服务器

    sock_addr = get_sockaddr_port("***", 80);

    if (connect(sock_fd, (struct sockaddr *) sock_addr, sizeof(struct sockaddr_in)) < 0) {

        printf("connect error: %s\n", strerror(errno));

        return -1;

    }

    // 读取数据

    char *data = get_data(sock_fd);

    if (data == NULL) {

        return -1;

    }

    // 关闭套接字

    close(sock_fd);

    return 0;

}

```

注意：这个示例仅用于演示目的。在实际应用中，需要考虑更多因素，如错误处理、超时设置和网络连接的安全性。

八、c语言怎样通过函数调用实现选择排序法？

c语言通过函数调用实现选择排序法：

1、写一个简单选择排序法的函数名，包含参数。int SelectSort(int * ListData,int ListLength);

2、写两个循环，在循环中应用简单选择插入排序：

int SelectSort(int * ListData,int ListLength)

{

int i , j ;

int length = ListLength;

for(i=0;i<=length-2;i++)

{

int k = i;

for(j=i+1;j<=length-1;j++)

{

if(ListData[k]>ListData[j])

{

k=j;

}

}

if(k!=i)

{

int tmp = ListData[i];

ListData[i] = ListData[k];

ListData[k] = tmp;

}

}

return 0;

}

3、对编好的程序进行测试，得出测试结果:

int main()

{

int TestData[5] = {34,15,6,89,67};

int i = 0;

printf("排序之前的结果\n");

for(i = 0;i<5;i++)

printf("|%d|",TestData[i]);

int retData = SelectSort(TestData,5);

printf("排序之后的结果：\n");

for(i = 0;i<5;i++)

printf("|%d|",TestData[i]);

return 0;

}

4、简单选择排序中，需要移动的记录次数比较少，主要的时间消耗在对于数据的比较次数。基本上，在比较的时候，消耗的时间复杂度为：n*n。

九、C语言冒泡排序？

将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为R.key的气泡。

根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。

如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

十、C语言多项排序？

1、稳定排序和非稳定排序

简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。

2、内排序和外排序

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；

在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

二、各类排序算法分析

1、冒泡排序

====================================================

算法思想简单描述：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的位置k，这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]

=====================================================

＃i nclude <iostream.h>

void BubbleSort(int* pData,int Count)

{

int iTemp;

for(int i=1;i<Count;i++)

{

for(int j=Count-1;j>=i;j--)

{

if(pData[j]<pData[j-1])

{

iTemp = pData[j-1];

pData[j-1] = pData[j];

pData[j] = iTemp;

}

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

BubbleSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情况)

第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)

第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)

第一轮：7,8,10,9->7,8,9,10(交换1次)

循环次数：6次

交换次数：6次

其他：

第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)

第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)

第一轮：7,8,10,9->7,8,9,10(交换1次)

循环次数：6次

交换次数：3次

上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。写成公式就是1/2*(n-1)*n。 现在注意，我们给出O方法的定义：

若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没 学好数学呀，对于编程数学是非常重要的！！！）

现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。

2、选择排序

====================================================

算法思想简单描述：

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度O(n2)--[n的平方]

====================================================

＃i nclude <iostream.h>

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i<Count-1;i++)

{

iTemp = pData[i];

iPos = i;

for(int j=i+1;j<Count;j++)

{

if(pData[j]<iTemp)

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

SelectSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情况)

第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)

第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)

第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)

循环次数：6次

交换次数：2次

其他：

第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)

第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)

第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)

循环次数：6次

交换次数：3次

遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n 所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

3、直接插入排序

====================================================

算法思想简单描述：

在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]

=====================================================

#include <iostream.h>

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i<Count-1;i++)

{

iTemp = pData[i];

iPos = i;

for(int j=i+1;j<Count;j++)

{

if(pData[j]<iTemp)

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

SelectSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情况)

第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)

第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)

第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)

循环次数：6次

交换次数：3次

其他：

第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)

第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)

第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)

循环次数：4次

交换次数：2次

上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些，所以我们浪费了时间。

个人认为在简单排序算法中，选择法是最好的。

4、希尔排序

====================================================

算法思想简单描述：

在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除

多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成

一组，排序完成。

下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1。

希尔排序是不稳定的。

=====================================================

这个排序非常复杂，看了程序就知道了。 首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序，以次类推。

＃i nclude <iostream.h>

void ShellSort(int* pData,int Count)

{

int step[4];

step[0] = 9;

step[1] = 5;

step[2] = 3;

step[3] = 1;

int i,Temp;

int k,s,w;

for(int i=0;i<4;i++)

{

k = step[i];

s = -k;

for(int j=k;j<Count;j++)

{

iTemp = pData[j];

w = j-k;//求上step个元素的下标

if(s ==0)

{

s = -k;

s++;

pData[s] = iTemp;

}

while((iTemp<pData[w]) && (w>=0) && (w<=Count))

{

pData[w+k] = pData[w];

w = w-k;

}

pData[w+k] = iTemp;

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};

ShellSort(data,12);

for (int i=0;i<12;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “我也不知道过程"，我们只有结果了。

5、快速排序

====================================================

算法思想简单描述：

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。它是由C.A.R.Hoare于1962年提出的。

显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的函数是用递归实现的，有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)

=====================================================

＃i nclude <iostream.h>

void run(int* pData,int left,int right)

{

int i,j;

int middle,iTemp;

i = left;

j = right;

middle = pData[(left+right)/2]; //求中间值

do{

while((pData[i]<middle) && (i<right))//从左扫描大于中值的数

i++;

while((pData[j]>middle) && (j>left))//从右扫描大于中值的数

j--;

if(i<=j)//找到了一对值

{

//交换

iTemp = pData[i];

pData[i] = pData[j];

pData[j] = iTemp;

i++;

j--;

}

}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left<j)，递归左半边

if(left<j)

run(pData,left,j);

//当右边部分有值(right>i)，递归右半边

if(right>i)

run(pData,i,right);

}

void QuickSort(int* pData,int Count)

{

run(pData,0,Count-1);

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

QuickSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况

1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。

2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。

第一层递归，循环n次，第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。

6、堆排序

====================================================

算法思想简单描述：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。

初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

====================================================

void sift(int *x, int n, int s)

{

int t, k, j;

t = *(x+s);

k = s;

j = 2*k + 1;

while (j

{

if (j

< *(x+j+1)) *判断是否满足堆的条件：满足就继续下一轮比较，否则调整。* && *(x+j) /> {

j++;

}

if (t<*(x+j))

{

*(x+k) = *(x+j);

k = j;

j = 2*k + 1;

}

else

{

break;

}

}

*(x+k) = t;

}

void heap_sort(int *x, int n)

{

int i, k, t;

int *p;

for (i=n/2-1; i>=0; i--)

{

sift(x,n,i);

}

for (k=n-1; k>=1; k--)

{

t = *(x+0);

*(x+0) = *(x+k);

*(x+k) = t;

sift(x,k,0);

}

}

void main()

{

#define MAX 4

int *p, i, a[MAX];

p = a;

printf("Input %d number for sorting :\n",MAX);

for (i=0; i

{

scanf("%d",p++);

}

printf("\n");

p = a;

select_sort(p,MAX);

for (p=a, i=0; i

{

printf("%d ",*p++);

}

printf("\n");

system("pause");

}

其他的交换法，双向冒泡法等等就不具体介绍了。

三、几种排序算法的比较和选择

1. 选取排序方法需要考虑的因素：

(1) 待排序的元素数目n；

(2) 元素本身信息量的大小；

(3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。

四、小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。

(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。