利用快速排序算法对结构体进行排序,首先按照 data 的值进行升序排列,若 data 值相等则按照 index 值进行升序排列。
- 对于该题若是数据量较少,可以使用的排序方式很多,比如:冒泡排序等等。
- 若是数据量较大,则应当选择时间复杂度较低的算法,快速排序算法则是比较好的选择。
- 快速排序的时间复杂度为 nlogn。
快速排序主要步骤
- 在数组中选择一个基准值(通常选择第一个元素为基准值);
- 将数组中小于基准值得数据移动到基准值的左边,大于基准值的数据移动到基准值的右边;
- 对于基准值左右两边的数据重复上述的两个步骤,直到每一个子集只有一个元素,即可认为是全部有序。
#include <iostream>
using namespace std;
struct Node_{
int index;
int data;
};
void quickSort(Node_* node, int begin, int end) {
if (begin < end) {
Node_ temp = node[begin];
int front = begin;
int rear = end;
while (front < rear) {
while (front < rear && node[rear].data > temp.data) {
rear--;
}
while (front < rear && node[rear].data == temp.data && node[rear].index > temp.index) {
rear--;
}
node[front] = node[rear];
while (front < rear && node[front].data < temp.data) {
front++;
}
while (front < rear && node[front].data == temp.data && node[rear].index <= temp.index) {
front++;
}
node[rear] = node[front];
}
node[front] = temp;
quickSort(node, begin, front - 1);
quickSort(node, front + 1, end);
}
else {
return;
}
}
int main() {
Node_ node[7] = { {2, 2}, {1, 2}, {5, 4}, {7, 7}, {4, 2}, {3, 4}, {9, 3} };
quickSort(node, 0, 6);
auto a = node;
return 0;
}
|