排序算法总结

一、冒泡排序

思想：相邻两个元素两两比较，小的放前，大的放后

时间复杂度：O(n^2)

排序算法的稳定性：稳定性

代码：

for(int j = len -1;j > 0;--j)
{
    for(i = 0;i < j;--j)
    {
        int t;
        t = a[i+1];
        a[i+1] = a[i];
        a[i] = t;
    }
}

二、选择排序

思想：在数组合适的位置上放上合适的数，选定一定的位置，从后面的数据与该数据进行比较。

1. 一次从待排序的数据元素中选出**最小（或最大）**的一个元素，存放在序列的起始(末尾)位置
2. 然后选出**次小(或次大)**的一个元素，存放在最大(最小)元素的下一个位置
3. 重复这样的步骤直到全部待排序的数据元素排完

时间复杂度：O(n^2)

排序算法的稳定性：不稳定性

代码：

for(int i = 0;i < len - 1;++i)
{
       for(int j = i+1;j < len;++j)
       {
            if(a[i]>a[j])
            {
                int t;
                t = a[i];
                a[i] = t;
            }
       }
}

三、插入法

思想：给数组a 排序，将数据进行插入，但是要保证数组，插入之后的鼠标线还是有序的。(保证插入的数据是，整体还是有序的)

时间复杂度：O(n^2)

排序算法的稳定性：稳定性

代码：

int b[len];
b[0] = a[0];
for(int i = 1;i < len;++i)
{
    int j;
    int t = a[i];
    j = i;
    while(j > 0 && a[j - 1] > t)
    {
        a[j] = a[j - 1];
        --j;
    }
    a[j] = t;
}

四、快速排序

1、先找基准数，一般指向begin 的

2、从右往左找第一个比基准数小的数，将该数放到begin的位置

3、从左往右找第一个比基准点大的数，将该数放到刚刚挪到的位置

4、继续转而执行2、3，直到最后一个元素为止，那么最后一个元素就存放哨兵元素了。

5、把小于哨兵元素的那一部分和大于哨兵元素的那一部分分别递归调用本函数，依次递归排序好所有元素；

6、运用递归的思想进行排序，首先通过基准点将数组划分为两半，后续将前半部分，进行遍历排序，排序好后，再按顺序执行，对后面的队列进行重新排序。

时间复杂度：O（nlogn）

稳定性：不稳定

代码：

void quick_sort(int *a, int begin, int end)
{
	if (begin >= end)
	{
		return ;
	}
	int i = begin;
	int j = end;
	int key = a[i];
	
	while (i < j)
	{
		while (i < j && a[j] >= key)
		{
			j--;
		}
		a[i] = a[j];
		while (i < j && a[i] <= key)
		{
			i++;
		}
		a[j] = a[i];
	}
	
	a[i] = key;
	quick_sort(a, begin, i-1);
	quick_sort(a, i+1, end);
}

五、二分查找

1. 思想 ：（前提）本身是有序的，将数据分为一半，看自己在那一半，继续一半一半的分
2. 时间复杂度 ；logn
3. end 跑到 begin 之前，说明数据查找完了，不在空间里面

代码：

int begin,end,mid;
begin = 0;
end = len -1;
while(begin <= end)
{
    mid = (begin + end)/2;
    if(a[mid] > n)
    {
        end = mid - 1;
    }
    else if(a[mid] < 1)
    {
    begin = mid +1;
    }
    else
    {
        break;
     }
}
if(begin <= end)
{
    printf("found = %d",a[mid]);
}

六、稳定性

相同的数据排序后，相同的数据的相对位置未发生改变