排序算法总结—时间复杂度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(" ");
// }

插入排序

适用于顺序链表和链式存储线性表。

查到i在有序数组中插入位置k
将有序数组中k到i-1位置所有元素依次后移一个位置
将元素复制到k的位置
注意哨兵的作用
可以采用折半查找进行优化，移动次数没有变化，但是减少了比较元素的次数。对于数据量不很大的顺序表，性能很好（仅适用于顺序存储线性表）

时间复杂度：O（n^2)
空间复杂度：O(1)
稳定的排序算法
对链表进行插入排序


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

排序算法总结—时间复杂度O(n^2)—冒泡/插入/选择小记

C/C++/C#相关栏目本月热门文章