排序算法01-交换排序

排序算法01-交换排序

一、链表冒泡排序

用两个指针即可，一个指针指向当前排序结点，另一个指针指向后续相邻结点，比较结点的数据大小并交换。内循环控制每趟排序的终止条件，外循环控制整个排序的终止条件。每一趟排序记录本次是否进行交换，若没有进行交换，则说明所有元素都有序，直接跳出外循环，否则将当前指针cur再次指向首元结点，进行下一次循环。

cur ： 遍历链表时进行元素交换元素tail ： 作为cur指针遍历的边界

/** * 时间复杂度为O(n^2) * (n-1) + ... + 3 + 2 + 1 */#includeusing namespace std;typedef struct node{ int data; struct node *next;}Node;Node* BubbleSort(Node* head){ if(head==NULL || head->next==NULL || head->next->next==NULL) return head; Node* cur = head->next; //cur指向首元结点 Node* tail = NULL; while(cur != tail){ bool isSwap = false; //此while循环就完成一趟排序，将一个大元素沉底 while(cur->next != tail){ if(cur->data > cur->next->data){ int temp; temp = cur->data; cur->data = cur->next->data; cur->next->data = temp; isSwap = true; } cur = cur->next; }// 此时一趟排序完成，cur指向最靠前的已排序元素 if(!isSwap) { break; } else{ //tail指向最靠前的已排序元素 tail = cur; cur = head->next; } } return head;}void show(Node* head){ Node* temp = head->next; while(temp != NULL) { cout<data<<" "; temp = temp->next; }}int main(){ Node* head = (Node*)malloc(sizeof(Node)); head->next = NULL; Node* tail = head;//尾插法创建 int nums[10] = {11,22,0,3,4,1,5,3,6,2}; int n = 10; for(int i=0; idata = nums[i]; temp->next = NULL; tail->next = temp; tail = temp; } cout<<"单链表创建完成，数据如下:"; show(head); head = BubbleSort(head); cout<

运行结果：

二、快速排序

/** * 时间复杂度为O(nlogn) */#includeusing namespace std;int partition(int* nums, int low, int high){ int value = nums[low]; while(low < high){ //首先用high游标找不大于value的值 while(nums[high]>=value && low

运行结果：

三、基数排序

1. 排序过程举例

降序排列【520，211，438，888，007，111，985，666，996，233，168】

第一趟（个位）分配结果：

第一趟收集结果：

此时得到的是个位元素递减的序列

注： 队头元素靠前，比如438在888和168前面

第二趟（十位）分配结果：

第二趟收集结果：

第三趟（百位）分配结果：

第三趟收集结果：

2. 基数排序的应用

3. 基数排序适用场景

四、桶排序

桶排序的思想很简单，就不写分析了

/** * @author Leo * 对于桶排序我们得知道排序元素的范围，比如当前元素范围为0 ~ 100 */const int range = 100;void BucketSort(vector& nums){ int* bucket = new int[range+1]();//所有元素必须初始化为0 for(int num : nums){ bucket[num]++; } int index = 0; for(int i = 0; i <= range; i++){ while(bucket[i]-- > 0){ nums[index++] = i; } } //for循环完成后，nums就是有序状态了}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。