本文将介绍python-插入排序的详细情况，特别是关于python给数据排序的相关信息。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于C#算法之冒泡排序、插入
本文将介绍python-插入排序的详细情况，特别是关于python给数据排序的相关信息。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于C#算法之冒泡排序、插入排序、选择排序、C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等、C语言 插入排序 Insert Sort、C语言实现常用排序算法——插入排序的知识。
本文目录一览：- python-插入排序（python给数据排序）
- C#算法之冒泡排序、插入排序、选择排序
- C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等
- C语言 插入排序 Insert Sort
- C语言实现常用排序算法——插入排序
python-插入排序（python给数据排序）
插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
图像分析
代码分析
def insert_sort(alist):
# 从第二个位置，即下标为1的元素开始向前插入
for i in range(1, len(alist)):
# 从第i个元素开始向前比较，如果小于前一个元素，交换位置
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)
时间复杂度
- 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
- 最坏时间复杂度：O(n2)
- 稳定性：稳定
C#算法之冒泡排序、插入排序、选择排序
冒泡排序法
是数组等线性排列的数字从大到小或从小到大排序。
以从小到大排序为例。
数据 11, 35, 39, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23
使用 数组 int [] array 存储数字。
过程 (数组从小到大排序)
思路循环都把最大的数放在最后一位，无序数字个数减1。
i 为当前任务位置，n 剩下的无序数字个数
从第 0位开始，比较前后两位数字大大小，当array[i] > array[i+1]时，数值互换。
一个循环后，数值最大的已经存到数组最后一位。
无序数字个数 n-1
for (int j = array.Length - 1; j > 0; j--) //每排一次，剩下的无序数减一
{
for (int i = 0; i < j; i++) //一个for循环获得一个最大的数
{
if (array[i] > array[i + 1]) //数值互换
{
var sap = array[i];
array[i] = array[i + 1];
array[i + 1] = sap;
}
}
}排序结果
动图如下
插入排序法
插入排序算法是把一个数插入一个已经排序好的数组中。
例如 把 22 插入到 [1,5,10,17,28,39,42] 中，
结果[1,5,10,17,22,28,39,42] 。
对数组使用插入排序法
数组 int [] array = [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];
数组元素是无序，设定一个从大到小或从小到大的方向，第一位就是有序的 [ 11 ] ，
第一次插入： [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]。
取第二个数跟第一个进行比较， 两位有序[11,39]
第二次插入：[11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]
取第三个数，[11, 39, 35],进行插入
[11,35, 39 ,30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]
... ...
以后每次取一个数，插入数组。
实现方法有很多种，笔者的方法跟冒泡排序法相似。
public static void ReSort(ref int[] array)
{
for (int i = 0; i < array.Length; i++) //要将第几位数进行插入
{
for (int j = i; j > 0; j--)
{
if (array[j] > array[j - 1]) break; //如果要排序的数大于已排序元素的最大值，就不用比较了。不然就要不断比较找到合适的位置
else
{
int sap = array[j];
array[j] = array[j - 1];
array[j - 1] = sap;
}
}
}
}试试把下面的代码复制到控制台，可以看到每次排序的结果。
using System;
namespace ConsoleApp1
{
class Program
{
public static void ReSort(ref int[] array)
{
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine("\n- - - - - - -");
Console.WriteLine("\n未排序前：");
for (int sun = 0; sun <= i && sun < array.Length; sun++)
{
Console.Write($"{array[sun]} , ");
}
for (int j = i; j > 0; j--)
{
if (array[j] > array[j - 1]) break;
else
{
int sap = array[j];
array[j] = array[j - 1];
array[j - 1] = sap;
}
}
Console.WriteLine("\n排序后： ");
for (int sun = 0; sun <= i && sun < array.Length; sun++)
{
Console.Write($"{array[sun]} , ");
}
}
}
static void Main(string[] args)
{
int[] array = new int[] { 11, 35, 39, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23 };
Console.Write("原数组：[");
foreach (var i in array)
{
Console.Write($"{i} , ");
}
Console.Write("]\n");
ReSort(ref array);
Console.Write("\n- - - - -\n最后结果：[");
foreach (var i in array)
{
Console.Write($"{i} , ");
}
Console.Write("]\n");
Console.ReadKey();
}
}
}
动图演示
冒泡排序法与插入排序法比较
- 冒泡排序是从一端开始，比较大小后存到另一端。每次都是从前开始，把最大或最小的结果放到最后。
- 插入排序始终是从前面开始，把下一个元素存到前面，不用比较最大最小的结果。
选择排序法
每次从后面找到最小或最大的数，进行位移排序。
数组 int [] array = [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];
第一位 i=0
最小值下标 minIndex = 0，最小值 min=11
从后面查找比 11 小的数，找到第 下标位 8，值为1，
进行交换,交换后[1, 39, 35, 30, 7, 36, 22, 13, 11, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];
第二位 i=1，
最小值下标 minIndex = 1，最小值 min=39,
从后面查找比 39 小且最小的数，找到 下标为 13，值为 5，
进行交换，交换后[1, 5, 35, 30, 7, 36, 22, 13, 11, 38, 26, 18, 12, 39, 45, 32, 6, 21, 42, 23];
public static void ReSort(ref int[] array)
{
for (int i = 0; i < array.Length; i++)
{
int min = array[i]; //设定第i位为最小值
int minIndex = i; //最小值下标
for (int j = i; j < array.Length; j++) //从第i为开始找出最小的数
{
if (array[j] < array[minIndex]) //重新存储最小值和下标
{
min = array[j];
minIndex = j;
}
}
if (array[i] != array[minIndex]) //如果到比第i为更小的数，则发生交换。找不到则不改变
{
array[minIndex] = array[i];
array[i] = min;
}
}
}动图如下
到此这篇关于C#算法之冒泡排序、插入排序、选择排序的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持。
您可能感兴趣的文章:
- C#实现冒泡排序和插入排序算法
- C#实现插入排序算法实例
- C#插入法排序算法实例分析
- C#折半插入排序算法实现方法
- C#实现插入排序
C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等
本文实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序
首先是算法实现文件Sort.h，代码如下：
/*
* 实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序
* 以及快速排序、归并排序、堆排序和LST基数排序
* @author gkh178
*/
#include <iostream>
template<class T>
void swap_value(T &a,T &b)
{
T temp = a;
a = b;
b = temp;
}
//插入排序：时间复杂度o(n^2)
template<class T>
void insert_sort(T a[],int n)
{
for (int i = 1; i < n; ++i)
{
T temp = a[i];
int j = i - 1;
while (j >= 0 && a[j] > temp)
{
a[j + 1] = a[j];
--j;
}
a[j + 1] = temp;
}
}
//冒泡排序：时间复杂度o(n^2)
template<class T>
void bubble_sort(T a[],int n)
{
for (int i = n - 1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (a[j] > a[j + 1])
{
swap_value(a[j],a[j + 1]);
}
}
}
}
//选择排序：时间复杂度o(n^2)
template<class T>
void select_sort(T a[],int n)
{
for (int i = 0; i < n - 1; ++i)
{
T min = a[i];
int index = i;
for (int j = i + 1; j < n; ++j)
{
if (a[j] < min)
{
min = a[j];
index = j;
}
}
a[index] = a[i];
a[i] = min;
}
}
//希尔排序：时间复杂度介于o(n^2)和o(nlgn)之间
template<class T>
void shell_sort(T a[],int n)
{
for (int gap = n / 2; gap >= 1; gap /= 2)
{
for (int i = gap; i < n; ++i)
{
T temp = a[i];
int j = i - gap;
while (j >= 0 && a[j] > temp)
{
a[j + gap] = a[j];
j -= gap;
}
a[j + gap] = temp;
}
}
}
//快速排序：时间复杂度o(nlgn)
template<class T>
void quick_sort(T a[],int n)
{
_quick_sort(a,n - 1);
}
template<class T>
void _quick_sort(T a[],int left,int right)
{
if (left < right)
{
int q = _partition(a,left,right);
_quick_sort(a,q - 1);
_quick_sort(a,q + 1,right);
}
}
template<class T>
int _partition(T a[],int right)
{
T pivot = a[left];
while (left < right)
{
while (left < right && a[right] >= pivot)
{
--right;
}
a[left] = a[right];
while (left < right && a[left] <= pivot)
{
++left;
}
a[right] = a[left];
}
a[left] = pivot;
return left;
}
//归并排序：时间复杂度o(nlgn)
template<class T>
void merge_sort(T a[],int n)
{
_merge_sort(a,n - 1);
}
template<class T>
void _merge_sort(T a[],int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
_merge_sort(a,mid);
_merge_sort(a,mid + 1,right);
_merge(a,mid,right);
}
}
template<class T>
void _merge(T a[],int mid,int right)
{
int length = right - left + 1;
T *newA = new T[length];
for (int i = 0,j = left; i <= length - 1; ++i,++j)
{
*(newA + i) = a[j];
}
int i = 0;
int j = mid - left + 1;
int k = left;
for (; i <= mid - left && j <= length - 1; ++k)
{
if (*(newA + i) < *(newA + j))
{
a[k] = *(newA + i);
++i;
}
else
{
a[k] = *(newA + j);
++j;
}
}
while (i <= mid - left)
{
a[k++] = *(newA + i);
++i;
}
while (j <= right - left)
{
a[k++] = *(newA + j);
++j;
}
delete newA;
}
//堆排序：时间复杂度o(nlgn)
template<class T>
void heap_sort(T a[],int n)
{
built_max_heap(a,n);//建立初始大根堆
//交换首尾元素，并对交换后排除尾元素的数组进行一次上调整
for (int i = n - 1; i >= 1; --i)
{
swap_value(a[0],a[i]);
up_adjust(a,i);
}
}
//建立一个长度为n的大根堆
template<class T>
void built_max_heap(T a[],int n)
{
up_adjust(a,n);
}
//对长度为n的数组进行一次上调整
template<class T>
void up_adjust(T a[],int n)
{
//对每个带有子女节点的元素遍历处理，从后到根节点位置
for (int i = n / 2; i >= 1; --i)
{
adjust_node(a,n,i);
}
}
//调整序号为i的节点的值
template<class T>
void adjust_node(T a[],int n,int i)
{
//节点有左右孩子
if (2 * i + 1 <= n)
{
//右孩子的值大于节点的值，交换它们
if (a[2 * i] > a[i - 1])
{
swap_value(a[2 * i],a[i - 1]);
}
//左孩子的值大于节点的值，交换它们
if (a[2 * i - 1] > a[i - 1])
{
swap_value(a[2 * i - 1],a[i - 1]);
}
//对节点的左右孩子的根节点进行调整
adjust_node(a,2 * i);
adjust_node(a,2 * i + 1);
}
//节点只有左孩子，为最后一个有左右孩子的节点
else if (2 * i == n)
{
//左孩子的值大于节点的值，交换它们
if (a[2 * i - 1] > a[i - 1])
{
swap_value(a[2 * i - 1],a[i - 1]);
}
}
}
//基数排序的时间复杂度为o(distance(n+radix)),distance为位数，n为数组个数，radix为基数
//本方法是用LST方法进行基数排序，MST方法不包含在内
//其中参数radix为基数，一般为10；distance表示待排序的数组的数字最长的位数；n为数组的长度
template<class T>
void lst_radix_sort(T a[],int radix,int distance)
{
T* newA = new T[n];//用于暂存数组
int* count = new int[radix];//用于计数排序，保存的是当前位的值为0 到 radix-1的元素出现的的个数
int divide = 1;
//从倒数第一位处理到第一位
for (int i = 0; i < distance; ++i)
{
//待排数组拷贝到newA数组中
for (int j = 0; j < n; ++j)
{
*(newA + j) = a[j];
}
//将计数数组置0
for (int j = 0; j < radix; ++j)
{
*(count + j) = 0;
}
for (int j = 0; j < n; ++j)
{
int radixKey = (*(newA + j) / divide) % radix; //得到数组元素的当前处理位的值
(*(count + radixKey))++;
}
//此时count[]中每个元素保存的是radixKey位出现的次数
//计算每个radixKey在数组中的结束位置，位置序号范围为1-n
for (int j = 1; j < radix; ++j)
{
*(count + j) = *(count + j) + *(count + j - 1);
}
//运用计数排序的原理实现一次排序，排序后的数组输出到a[]
for (int j = n - 1; j >= 0; --j)
{
int radixKey = (*(newA + j) / divide) % radix;
a[*(count + radixKey) - 1] = newA[j];
--(*(count + radixKey));
}
divide = divide * radix;
}
}
然后是测试文件main.cpp，代码如下：
#include "Sort.h"
using namespace std;
template<class T>
void printArray(T a[],int n)
{
for (int i = 0; i < n; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
for (int i = 1; i <= 8; ++i)
{
int arr[] = { 45,38,26,77,128,25,444,61,153,9999,1012,43,128 };
switch (i)
{
case 1:
insert_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 2:
bubble_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 3:
select_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 4:
shell_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 5:
quick_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 6:
merge_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 7:
heap_sort(arr,sizeof(arr) / sizeof(arr[0]));
break;
case 8:
lst_radix_sort(arr,sizeof(arr) / sizeof(arr[0]),10,4);
break;
default:
break;
}
printArray(arr,sizeof(arr) / sizeof(arr[0]));
}
return 0;
}
最后是运行结果图，如下：
以上就是C++实现八个常用的排序算法的全部代码，希望大家对C++排序算法有更进一步的了解。
C语言 插入排序 Insert Sort
#include <stdio.h>
void exchange(int* array, int p1, int p2)
{
if (p1 == p2)
return;
int temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
void insertSort(int* array, int len)
{
int sorted = 0; //the 1st data we think was already sorted
int cur;
for (cur = 1; cur < len; cur++)//start from 2nd data
{
//loop with sorted range
int sort;
for (sort = 0; sort <= sorted; sort++)
{
if (array[cur] <= array[sort])
{
// let current data move forward one by one and stop at right postion
int curPos = cur;
while (curPos != sort)
{
exchange(array, curPos, curPos - 1);
curPos--;
}
break;
}
}
sorted++;
}
}
//From Intruduction Of Alogrithim
void insertSort1(int* array, int len)
{
for (int i = 1; i < len; i++)//loop start from 2nd data cause we think 1st is already sorted
{
int key = array[i];//current data we call it key
int j = i - 1;//watch pre data of key
while (j >= 0 && array[j] > key)
{
array[j+1] = array[j];//if pre data bigger, move to right
j--;//if pre data stiill bigger than key, move to right
}//end while for moving
array[j + 1] = key;// when move over the postion `j+1` was empty insert the key
}
}
void main()
{
intarray[10] = { 1, 8, 3, 6, 2, 4, 7, 5, 9, 0 };
printf("before:");
int i;
for (i = 0; i <= sizeof(array) - 1; i++)
{
printf("%d ", array[i]);
}
printf("\n");
insertSort(array, sizeof(array));
printf("\n after:");
for (i = 0; i <= sizeof(array) - 1; i++)
{
printf("%d ", array[i]);
}
return;
}
C语言实现常用排序算法——插入排序
插入排序是最基础的排序算法，原理：
首先1个元素肯定是有序的，所以插入排序从第二个元素开始遍历；
内循环首先请求一个空间保存待插入元素，从当前元素向数组起始位置反向遍历；
当发现有大于待插入元素的元素，则将此元素向后挪一位，最终将缓冲区的元素放入空白位置。
void insert_sort(int a[],int n) {
int i,j,temp;
for(i=1; i<n; i++) {
temp=a[i];
for(j=i; j>0; j--) {
if(temp<a[j-1]) {
a[j]=a[j-1];
}else{
break;
}
}
a[j]=temp;
}
}有图有真相：
关于python-插入排序和python给数据排序的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于C#算法之冒泡排序、插入排序、选择排序、C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等、C语言 插入排序 Insert Sort、C语言实现常用排序算法——插入排序等相关内容，可以在本站寻找。
本文标签：
