排序算法收录

 

基础语言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;
    }

 

...

附录