• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

史上最全的排序算法讲解–作为程序员的你一定要知道

互联网 diligentman 1小时前 2次浏览

史上最全的排序算法讲解--作为程序员的你一定要知道

一、冒泡排序算法
算法性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、稳定排序 4、原地排序
过程简单描述:
1、把第一个元素与第二个元素比较,如果第一个比第二个大,则交换他们的位置。接着继续比较第二个与第三个元素,如果第二个比第三个大,则交换他们的位置….

2、我们对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样一趟比较交换下来之后,排在最右的元素就会是最大的数。

3、除去最右的元素,我们对剩余的元素做同样的工作,如此重复下去,直到排序完成。

4、为方便理解我还准备了动图:
史上最全的排序算法讲解--作为程序员的你一定要知道
c代码实现


int* bubbleSort1(int arr[] ,int n) 
{
if (arr == NULL || n < 2) {  return arr; }
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n - i - 1; j++)
    {
        if (arr[j + 1] < arr[j])
        {
            flag = 0;
           swap_2_num(arr[j + 1],arr[j]);
        }
    }
}
return arr;
}

冒泡排序改进版c


int* bubbleSort1(int arr[] ,int n) 
{
if (arr == NULL || n < 2) {  return arr; }
for (int i = 0; i < n; i++)
{
    int flag = 1; //标志位
    for (int j = 0; j < n - i - 1; j++)
    {
        if (arr[j + 1] < arr[j])
        {
            flag = 0;
           swap_2_num(arr[j + 1],arr[j]); 
           //swap_2_num交换两个数函数
        }
    }
    //一趟下来是否发生位置交换
    if (flag) {break;}
}
return arr;
}

python代码实现

def bubble_sort(mylist): 
	for i in range(0,len(mylist)-1): #n个元素 共有n-1趟
		for j in range (i+1,len(mylist)):
			if mylist[i]<mylist[j]:
				mylist[i],mylist[j] = mylist[j],mylist[i]
	return mylist

冒泡排序改进版-python

def bubble_advance(mylist): 
	for i in range(0,len(mylist)-1): #n个元素 共有n-1趟
		flag = True
		for j in range (i+1,len(mylist)):
			if mylist[i]>mylist[j]:
				flag = False
				mylist[i],mylist[j] = mylist[j],mylist[i]
		if flag:
			break
	return mylist

二、选择排序
性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、非稳定排序 4、原地排序
过程简单描述:
1、首先,找到数组中最小的那个元素
2、其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。
3、其次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。
4、如此往复,直到将整个数组排序。这种方法我们称之为选择排序。
为方便理解我还准备了动图:
史上最全的排序算法讲解--作为程序员的你一定要知道
c代码实现

int* selectSort(int a[],int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[min] > a[j]) 
            {
                min = j; 
            }
        }
        swap_2_num(a[i],a[min]);
    }
    return a;
}

python代码实现

def choice(mylist):
	for i in range(0,len(mylist)-1):  #比较len-1趟.先选第一个为最小值
		index = i#选一个最小值     # 记录最小数的索引
		for j in range(i+1,len(mylist)): #把最小值与后面的每一个进行比较
			if mylist[index] < mylist[j]:
				index = j ##改变最小值  i不是最小数时,将 i 和最小数进行交换
		if index !=i: ##如果最小值有变 则对调
			mylist[index] ,mylist[i] =mylist[i] ,mylist[index]
	return mylist

三、插入排序
性质:1、时间复杂度:O(n2) 2、空间复杂度:O(1) 3、稳定排序 4、原地排序

我们在玩打牌的时候,你是怎么整理那些牌的呢?一种简单的方法就是一张一张的来,将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候,为了要插入元素,我们需要腾出空间,将其余所有元素在插入之前都向右移动一位,这种算法我们称之为插入排序。

过程简单描述:
1、从数组第2个元素开始抽取元素。
2、把它与左边第一个元素比较,如果左边第一个元素比它大,则继续与左边第二个元素比较下去,直到遇到不比它大的元素,然后插到这个元素的右边。
3、继续选取第3,4,….n个元素,重复步骤 2 ,选择适当的位置插入。
为方便理解我还准备了动图:
史上最全的排序算法讲解--作为程序员的你一定要知道
c代码实现

int * insertsort(int arr[],int len)
{
    if (arr == NULL || len < 2) { return arr; }
    for (int i =1;i<len;i++)
    {
        int index = i;
        while (index>0 && arr[index]<arr[index-1])
        { 
            swap_2_num(arr[index],arr[index-1]);
            index -=1;
        }
    }
    return arr;
}

python代码实现


def insert_sort(arr): 
	for i in range(1,len(arr)):
		index = i
		while index>0 and  arr[index-1] > arr[index]:
			(arr[index],arr[index-1]) = (arr[index-1],arr[index])
			index =index-1
	return arr

后续进步补充…

参考链接 1
参考链接2


喜欢 (0)