数据结构-排序-快速排序
1.算法思想
快速排序的思想： 从n个记录中选取一个记录（这里选取第一个记录），使得排序码小于它的记录全都放在它的左边，大于它的都放在右边，然后对它的左右两边重复这个过程，直到所有记录都位于正确的位置。具体做法： 先将第一个记录（记录记为 x ）暂存，这样子就空出了第一个位置，这个位置将要放置排序码不大于x的记录，从右到左找到一个排序码不大于x的记录，将它放在第一个位置；然后后面就又有一个空位，我们要放入一个排序码大于x的记录，从左到右找到一个排序码大于的记录，放入后面的空白的位置，循环这个过程，直到两边的下标指向同一个位置时，就将x记录放入这个位置，完成划分，实现x的左边都是小于它的记录，右边都是大于它的记录。图片来自与菜鸟教程
2.算法复杂度
执行时间： O(nlogn)附加空间： 一个中点储存空间和要考虑递归的空间是否是稳定的排序方法： 不稳定
3.算法实现
#include
"stdio.h"
#define MAXSIZE
10
typedef
int keytype
;
typedef struct
{
keytype key
;
int other
;
}recordtype
;
typedef struct
{
int length
;
recordtype r
[MAXSIZE
+ 1];
}table
;
void quicksort(table
* tab
, int left
, int right
) {
int i
, j
;
i
= left
;
j
= right
;
if (left
<right
)
{
tab
->r
[0] = tab
->r
[i
];
do {
while (tab
->r
[0].key
< tab
->r
[j
].key
&&i
< j
) j
--;
tab
->r
[i
] = tab
->r
[j
];
while (tab
->r
[0].key
> tab
->r
[i
].key
&&i
< j
) i
++;
tab
->r
[j
] = tab
->r
[i
];
} while (i
!= j
);
tab
->r
[i
] = tab
->r
[0];
quicksort(tab
, left
, i
- 1);
quicksort(tab
, i
+ 1, right
);
}
}
void inputData(table
* tab
) {
printf("please input the length:\n");
scanf("%d", &tab
->length
);
printf("please input the data:");
for (int i
= 1; i
<= tab
->length
; i
++)
{
scanf("%d", &tab
->r
[i
].key
);
}
return tab
;
}
void show(table
* tab
) {
printf("the result data:");
for (int i
= 1; i
<= tab
->length
; i
++)
{
printf("%d ", tab
->r
[i
].key
);
}
}
void main() {
table
* tab
= malloc(sizeof(table
));
inputData(tab
);
quicksort(tab
, 1, tab
->length
);
show(tab
);
}
运行截图
欢迎大家关注我的博客：breeziness123 转载说明出处
