python 排序基础练习

# 降序
#插入排序
def list_change(xulie):

    for j in range(1,len(xulie)):  # 确定循环次数
        print("待比较的值是：",xulie[j],"区域范围是0~",j)
        #for i in range(j-1,-1,-1):  # 大范围内的循环，疆
        while j>=1:
            if xulie[j-1] > xulie[j]:
                xulie[j-1],xulie[j] = xulie[j],xulie[j-1]
                j -= 1
                print(j,">>",xulie)
            else:
                break
        print(xulie)


# 希尔排序
def shell_sort(alist):
    if not alist:
        return
    n=len(alist)
    gap=n//2
    while gap>0:
        for i in range(gap,n):
            while i-gap>=0:
                if alist[i]<alist[i-gap]:
                    alist[i],alist[i-gap]=alist[i-gap],alist[i]
                    i-=gap
                else:
                    break
            print(gap,":",alist)
        gap//=2


# 冒泡排序的思路在于把每一次遍历结果的最小值放在最左边,下一次遍历时，缩小范围
def maopao(x):
    for i in range(len(x)):
        print(f"第{i}次排序：待排序的区域范围是{0}~{len(x)-i-1}")
        for j in range(1,len(x)-i):
            if x[j] < x [j-1]:
                x[j],x[j-1]= x[j-1],x[j]
                print(j, ">>", xulie)
    print(x)

# 冒泡排序的改进版鸡尾酒排序
def jiweijiu(x):

    count=0
    for i in range(len(x)):
        print(f"第{i}次排序：待排序的区域范围是{0}~{len(x)-i-1}")
        for j in range(i,len(x)-i):
            print(j, ">>", xulie)
            if x[j] < x [j-1]:
                x[j],x[j-1]= x[j-1],x[j]
                count +=1
        for j in range(len(x)-i-1,i,-1):
            print(j, "<<", xulie)
            if x[j] < x[j - 1]:
                x[j], x[j - 1] = x[j - 1], x[j]
                count += 1
    print(f"总共完成{count}次排序 ，结果为{x}")

#选择排序，每一次遍历将序列中找到最小值，并放置到序列前。指针法
def choose_sort(x):
    for i in range(len(x)):
        print(f"第{i}次排序：待排序的区域范围是{i}~{len(x)-1}")
        min = x[i]
        t=i
        for j in range(i,len(x)):
            if x[j]<min:
                t=j
                min = x[j]

        print(f"第{i}次查找：{x},最小值位置在{t},值为{min}",)
        x[i],x[t] = x[t],x[i]
    print(x)

# 最值排序2,选择排序的一种。总结，排序方法千万种，优化效率，有效降低时间复杂度是更高阶排序方法的所追求的。将选择到最值放在做左侧
def zuizhi(raw):
    for i in range(len(raw)):
        print(f"第{i}次排序：{raw}")
        for j in range(i, len(raw)):
            if raw[i] > raw[j]:
                raw[i], raw[j] = raw[j], raw[i]
                print(f"发生一次{i}和{j}的交换，交换后结果为{raw}")
    print(raw)

1、关于排序有多种方法，本次练习仅在理解范围内，选择了，插入排序、选择排序、冒泡排序、希尔排序进行练习。

2、除了希尔排序的时间复杂度较低O(nlogn)，其他排序都是O(n^2)

3、本次练习中所有排序的思路基本一致，就是进行一次大循环，每一次循环，都完成一次遍历并完成目标任务（规定动作）。只要规定动作保持一致，并限定在规定范围内处理，就可以达成排序效果。

比如，冒泡排序的要求是，一次循环将最大或最小值，移动到右侧，下一次循环时缩小遍历范围；插入排序，通过不断插入数值，使得原有有序的范围不断扩大，直到整个序列都为有序；选择排序，每一次循环遍历时都将最小值通过索引或者交换的方式，移动到最左侧，并相应缩小遍历范围。希尔排序是利用斐波那契数列的原理，优化了插入排序，最后一个步长gap=1

4、排序的过程要确定，符合怎样条件的哪两个值之间，如何交换位置，规则是什么，每次循环遍历的范围是什么。

5、排序方法多种多样

6、对于python而言，sort似乎最为便捷。sort方法，返回值为None，列表本身被修改。sorted函数是返回一个新的有序列表。sort默认均为升序。reversed函数是反转原有序列，并不做排序处理比如：

xulie = [9,8,7,16,5,4,3,2,1,0]
xulie2 = [0, 1, 2, 3, 4, 5, 16, 7, 8, 9]
print(xulie.sort(reverse=True),xulie)
print(sorted(xulie2,reverse=True),xulie2)
print(list(reversed(xulie2)),xulie2)

None [16, 9, 8, 7, 5, 4, 3, 2, 1, 0]
[16, 9, 8, 7, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 16, 7, 8, 9]
[9, 8, 7, 16, 5, 4, 3, 2, 1, 0] [0, 1, 2, 3, 4, 5, 16, 7, 8, 9]

Process finished with exit code 0