排序算法总结—时间复杂度O(n^2)—冒泡/插入/选择小记
冒泡排序
最基础的排序，一层一层将最大值或最小值放到该去的位置。
适用于顺序存储和链表存储
- 时间复杂度：O（n^2)
- 空间复杂度：O(1)
- 稳定的排序算法
- 产生的有序子序列全局有序，每次有一个元素放到最终的的位置上。
移动零例题：给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
void moveZeroes(int* nums, int numsSize){ // if(numsSize == 1) return nums; int index = 0; bool find = true; for(int i = 0;index < numsSize&&find == true;i++) { if(i == numsSize) { break; } if(nums[i] == 0) { index = i; find = false; // printf("%d",nums[index-1]); for(int j = index;j < numsSize-1;j++) { if(!find) { if(nums[j+1] == 0) { index = j-1; find = true; } } swap(nums,j+1,j); } numsSize--; i = index; } } } void swap(int nums[],int i,int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
选择排序
对于选择排序的基本思想，每一趟在待排序元素（n-i+1）中选择关键字最小的元素，作为有序子序列第i个元素。
优化：我们可以一趟排序中同时确定最大最小值，放到对应的位置。对于最大最小值下标一样的时候，表明该序列已经有序。同时注意当标注的下标为i时，要和之前与i进行交换的元素交换。看代码很清楚～
时间复杂度：O（n^2)
空间复杂度：O(1)
不稳定的排序算法 （on方算法中唯一不稳定的算法）
数组中的第k个最大元素：
给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
int findKthLargest(int* nums, int numsSize, int k){ int maxindex,minindex; int i,j; for(i = 0;i < numsSize/2;i++) { maxindex = i; minindex = i; for(j = i+1;j < numsSize-i;j++) { if(nums[maxindex] < nums[j]) { maxindex = j; } if(nums[minindex] > nums[j]) { minindex = j; } } if(maxindex == minindex) break; swap(nums,maxindex,i); // print(nums,numsSize); if(minindex == i) { minindex = maxindex; } swap(nums,minindex,numsSize-1-i); // print(nums,numsSize); } return nums[k-1]; } void swap(int arr[],int i,int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // void print(int nums[],int numsSize) // { // for(int m = 0;m < numsSize;m++) // { // printf("%d",nums[m]); // } // printf(" "); // }
插入排序
适用于顺序链表和链式存储线性表。
1.查到i在有序数组中插入位置k
2.将有序数组中k到i-1位置所有元素依次后移一个位置
3.将元素复制到k的位置
注意哨兵的作用
可以采用折半查找进行优化，移动次数没有变化，但是减少了比较元素的次数。对于数据量不很大的顺序表，性能很好（仅适用于顺序存储线性表）
时间复杂度：O（n^2)
空间复杂度：O(1)
稳定的排序算法
对链表进行插入排序
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* insertionSortList(struct ListNode* head){ if(head == NULL || head->next == NULL) { return head; } struct ListNode *l = (struct ListNode *)malloc(sizeof(struct ListNode)); l->val = 0; l->next = head; struct ListNode *pre = head; struct ListNode *cur = head->next; //cur外循环遍历 while (cur != NULL) { if(pre->val <= cur->val) { pre = pre->next; } else { struct ListNode *move = l; while(move->next->val <= cur->val) { move = move->next; } //每次都从链表头寻找位置插入 pre->next = cur->next; cur->next = move->next; move->next = cur; } cur = pre->next; } return l->next; }
完结！over！冲冲冲，冲累了，找小哥哥聊天hhh💖
