十大排序、七大查找算法python实现——选择排序(selection sort)

原理参考链接：https://www.cnblogs.com/onepixel/articles/7674659.html

 

选择排序的原理是，在无序数组中找到最小或最大的元素，然后将其移动至无序数组的最右或最左边，逐渐形成有序数组。具体实施步骤如下：

初始状态：无序区为R[1..n]，有序区为空；
	
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
	
n-1趟结束，数组有序化了。
def selection_sort(L):
    n = len(L)
    
    for i in range(n-1):  # 执行n-1次
        min_index = i  #  获取无序数组的第一个元素的下标
        for j in range(i+1, n):  # 扫描无序数组中最小的元素
            if L[min_index] > L[j]:
                min_index = j  # 返回最小元素的下标
        if i != min_index:
            L[min_index], L[i] = L[i], L[min_index] # 将最小元素与无序数组的第一个元素交换位置
        print(L)
    return

执行结果如下，我们可以看到，随着算法的不断执行，右侧无序数组中的最小元素逐渐移向左侧位置。

题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0
方法一
先利用sort函数排序，从第一个元素查找到中间元素，如果存在相隔数组长度一半及以上位置的元素相等的话（好难描述…），判定成功，返回该元素。这个方法操作比较麻烦，需要考虑数组左右，并且需要考虑数组的长度奇偶。
牛客AC代码如下
import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         
         
        int temp=0;
        if(array.length==0||array==null){
            return 0;
        }else if(array.length==1)
            return temp=array[0];
         else if(array.length==2&&array[0]!=array[1])
             return temp=0;
        else{
            Arrays.sort(array);
            for (int i = 0; i < array.length/2; i++) {
                if(array[i]==array[array.length-1-i] || (array[i]==array[array.length/2]&&array.length%2==0))
                     temp=array[i];
                if(array[array.length/2]==array[array.length-1] && array.length%2!=0)
                    temp=array[array.length/2];
            }
            return temp;
        }
         
             
         
         
     
    }
}


方法二
建立一个count方法统计数组中每个元素出现的次数num，并返回。在判定方法里调用count方法，如果num大于数组长度一半，判定成功。这个方法不需要考虑数组奇偶，比较好理解。
牛客AC代码如下
import java.util.Arrays;
public class Solution {
        private int count(int x,int[] array) {
		// TODO 自动生成的方法存根
		int num=0;
		for (int i = 0; i < array.length; i++) {
			if(x==array[i])
				num++;
		}
		
		return num;

	}
public int MoreThanHalfNum_Solution(int [] array) {
	int num=0;
	for (int i = 0; i < array.length; i++) {
		if(count(array[i], array)>array.length/2){
			num=array[i];
		}
			
		
	}
	return num;
	
	
	
} 
}

文章目录
语法简单说明
插入排序InsertionSort
选择排序SelectionSort
版本一
版本二，优化
希尔排序ShellSort
冒泡排序BubbleSort
版本一
版本二
快速排序QuickSort
版本一，双路
版本二 ，三路
合并排序MergeSort
堆排序

语法简单说明
using namespace std;
template <typename T>

插入排序InsertionSort

查找出arr(i)在L[1…i-1]中的插入位置k
将arr[k…i-1]中所有元素全部后移一个位置
将arr(i)复制到arr(k)

void insertionSort( T arr[], int n){    //插入排序
    for(int i = 1; i < n; i++){    //插入排序从i= 1开始，因为第一个元素从一开始就已经有序了
        //寻找元素arr[i]合适的插入位置
//        for(int j = i; j>0; j--)  //循环到最后j=1,判断与j=0位置的元素是否交换,相对于选择排序，第二层循环会提前结束
//            if( arr[j] <  arr[j-1])
//                swap(arr[j], arr[j-1]);
//            else
//                break;
//或者采用下面的方法，将判断放在for循环中
//        for(int j = i; j>0&&arr[j] <arr[j-1];j--){
//            swap(arr[j],arr[j-1]);
//        }
        //经过优化后的代码
        T e = arr[i];
        int j;    //j保存元素e应该插入的位置
        for(j = i; j>0 && arr[j-1] > e; j--){
            arr[j] = arr[j-1];    //把j-1位置的元素向后挪一下
        }
        arr[j] = e;
    }
}

#插入排序Python版
def insertion_sort(a):
    for i in range(1,len(a)):
        cur = a[i]
        j = i
        while j>0 and a[j-1]>cur:
            a[j] = a[j-1]
            j -= 1
        a[j] = e
    return a

选择排序SelectionSort
版本一
void selectionSort( T arr[], int n){    //选择排序
    for(int i = 0; i < n; i++){
        //寻找[i, n)区间的最小值
        int minIndex = i;
        for( int j = i+1; j<n;j++)
            if(arr[j] < arr[minIndex])
                minIndex = j;
        swap( arr[i], arr[minIndex]);  // C++标准库
    }
}

版本二，优化
在每一轮中, 可以同时找到当前未处理元素的最大值和最小值
void selectionSort(T arr[], int n){

    int left = 0, right = n - 1;
    while(left < right){
        int minIndex = left;
        int maxIndex = right;
        // 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
        if(arr[minIndex] > arr[maxIndex])
            swap(arr[minIndex], arr[maxIndex]);

        for(int i = left + 1 ; i < right; i ++)
            if(arr[i] < arr[minIndex])
                minIndex = i;
            else if(arr[i] > arr[maxIndex])
                maxIndex = i;

        swap(arr[left], arr[minIndex]);
        swap(arr[right], arr[maxIndex]);

        left ++;
        right --;
    }

    return;
}

#直接选择排序Python版
def selection_sort(a):
    for i in range(len(a)-1):
        min_index = i
        for j in range(i+1, len(a)):
            if a[j]<a[min_index]:
                min_index = j
        if i != min_index:
            a[i], a[min_index] = a[min_index], a[i]
    return a

希尔排序ShellSort
void shellSort(T arr[], int n){
     // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while(h < n/3)
        h = 3 * h + 1;    //取一个步长

    while(h >= 1){
        for( int i = h; i <n ; i++){
            //对arr[i], arr[i-h], arrr[i-2*h], arr[i-3*h]...使用插入排序
            T e = arr[i];
            int j;
            for( j=i; j >= h&& e<arr[j-h]; j-=h)
                arr[j] = arr[j-h];     //从后往前寻找插入位置
            arr[j]=e;
        }
        h/=3;
    }
}

冒泡排序BubbleSort
版本一
void bubbleSort( T arr[] , int n){
    bool swapped;
    do{
        swapped = false;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
                swapped = true;
            }
        // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
        // 所以下一次排序, 最后的元素可以不再考虑
        n --;
    }while(swapped);
}

版本二
// 我们的第二版bubbleSort,使用newn进行优化
template<typename T>
void bubbleSort2( T arr[] , int n){

    int newn; // 使用newn进行优化
    do{
        newn = 0;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;
            }
        n = newn;
    }while(newn > 0);
}

#冒泡排序
def bubble_sort(a, n):
    ac = a.copy()
    swap_size = 1
    while swap_size > 0:
        swap_size = 0
        for i in range(n-1):
            if ac[i] > ac[i+1]:
                ac[i], ac[i+1] = ac[i+1], ac[i]
                swap_size += 1
        n -= 1
    return ac

快速排序QuickSort
// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){

    if( l >= r )
        return;
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1 );
    __quickSort(arr, p+1, r);
}

版本一，双路
int __partition2(T arr[], int l, int r){    //双路快速排序

    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];

    //arr[l+1...i) <= v;  arr(j...r] >= v
    int i = l+1, j = r;
    while(true){
        while(i <=r && arr[i] <v) i++;
        while(j >= l+1 && arr[j] > v) j--;
        if( i> j) break;
        swap( arr[i], arr[j] );
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

版本二 ，三路
// 递归的三路快速排序算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){

    // 对于小规模数组, 使用插入排序进行优化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }

    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );

    T v = arr[l];

    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }

    swap( arr[l] , arr[lt] );

    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}

合并排序MergeSort
void MergeSort(T A[], int low, int high){
    if(low < high){
        int mid = (low+high)/2;  //从中间划分两个子序列
        MergeSort(A, low, mid);  //对左侧子序列进行递归排序
        MergeSort(A, mid, high);
        Merge(A, low, mid, high); //归并
    }
}

void Mereg( T A[], int low, int mid, int high){
    //表A的两段A[low...mid]和A[mid+1...high]各自有序，将他们合成一个有序表
    T B[high-low+1];
    for (int k = low; k < high; ++k) 
        B[k] = A[k];
    for (int i=low, j=mid+1, k=i; i<=mid && j<=high ; k++) {
        if(B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    } //for
    
    while(i<=mid) A[k++] = A[i++];  //若左半部分未检测完，复制
    while(j<=high) A[k++] = A[j++];
}

堆排序
//创建一个大根堆
void BuildMaxHeap(T A[], int len){
    for (int i = len/2; i > 0; i--)
        AdjustDown(A, i, len);
}

void shiftUp(int k){               
    while( k>1 && data[k/2] < data[k]){   
        swap(data[k/2], data[k]);
        k /= 2;
    }
}

void AdjustDown(T A[], int k, int len){
    //将元素k向下调整
    T e = A[k];
    for (int i = 2*k; i <= len; i*=2) {
        if(i<len&&A[i]<A[i+1])
            i++;
        if(e>=A[i]) break;
        else{
            A[k] = A[i];
            k=i;
        }
    }
    A[k] = e;
}

void HeapSort(T A[], int len){
    BuildMaxHeap(A, len);     //初始建堆
    for (int i = len; i > 1 ; i--) {
        Swap(A[i], A[1]);    // 输出堆顶元素（和堆底元素进行交换）
        AdjustDown(A, 1, i-1);  //剩余i-1个元素整理成堆

    }
}

服务器上传文件失败了,才开始没考虑到磁盘原因还以为是自己的scrt的问题,还好df -h看了下,最后发现磁盘满了,真是…
find / -type f -print0 | xargs -0 du -h | sort -rh | head -n 10

详解
find //在目录结构中搜索文件的命令

/ //在整个系统（从根目录开始）中查找

-type //指定文件类型

f //普通文件

-print0 //在标准输出显示完整的文件名，其后跟一个空字符（null）

| //控制操作符，将一条命令的输出传递给下一个命令以供进一步处理

xargs //将标准输入转换成命令行参数的命令

-0 //以空字符（null）而不是空白字符（LCTT 译者注：即空格、制表符和换行）来分割记录

du -h //以可读格式计算磁盘空间使用情况的命令

sort //对文本文件进行排序的命令

-r //反转结果

-h //用可读格式打印输出

head //输出文件开头部分的命令

n -10 //打印前 10 个文件