排序算法收录

标签: 排序

 

基础语言Python

1 选择排序

思想:

在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

操作方法:

第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

以此类推.....

第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

直到整个序列按关键码有序。

实战:

import random
arr = []    #没有定义长度,长度为0
#随机生成一个数组
def getArray(n):
    for i in range( 10 ):   #  0,1,2,3,4,5...
        #arr[i]    则下标越界
        arr.append( random.randint(0,999) )

print('待排序的数组')
getArray(10)        #调用这个函数,生成随机数组
#选择排序
def show(arr): 
    for i in range( len(arr) ):
        print(arr[i],end=' ')
    print('\n')

show( arr )     #显示刚刚产生的随机数组
#选择排序算法一
print('选择排序算法一')

for i in range( len(arr)-1 ):
    for j in range( i+1,len(arr) ):
        if arr[j]<arr[i]:
            temp = arr[j]
            arr[j] = arr[i]
            arr[i] = temp
show(arr)


#选择排序算法二
print('选择排序算法二')

for i in range( len(arr)-1 ):
    index = i
    for j in range( i+1,len(arr) ):
        if arr[index]>arr[j]:
            index = j
    arr[i],arr[index] = arr[index],arr[i]  #将arr[index]与arr[i]数据交换
show(arr)

 

2 冒泡排序

从前往后,依次比较相邻的两个数,把较大的数放到后面。一次循环,可以在当前最末尾位置得到一个当前最大值

实战:

#冒泡排序
#外循环    len(arr)-1

#内循环    len(arr)-i-1

#相邻的两个元素比较
getArray(10)
print('待排序的数组')
show(arr)

print('起泡排序算法')

for i in range( len(arr)-1 ):
    for j in range( len(arr)-i-1 ):
        if arr[j]>arr[j+1]:
            temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp
show(arr)

输出结果如下:

3、插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

3.1 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;

  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;

  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;

  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

  • 将新元素插入到该位置后;

  • 重复步骤2~5。

3.2 动图演示

/**
     * 插入排序
    * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }

 

...

附录

原文链接:加载失败,请重新获取