Python排序:Python中的排序方法和算法

学习如何使用Python中的Sort函数对列表、数组、字典等进行排序,使用Python中的各种排序方法和算法:

排序是一种技术,用于按照升序或降序的顺序对数据进行排序。

大多数时候,大型项目的数据没有按照正确的顺序排列,这在有效访问和获取所需数据时产生了问题。

分拣技术被用来解决这个问题。 Python提供了各种分拣技术 例如: 泡沫排序、插入排序、合并排序、快速排序等。

在本教程中,我们将通过使用各种算法了解Python中的排序工作。

Python排序

Python排序的语法

为了进行排序,Python提供了内置函数,即 "sort() "函数。 它被用来对列表中的数据元素按升序或降序进行排序。

让我们通过一个例子来理解这个概念。

例1:

 ```a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( " List in ascending order: ", a ) ```. 

输出:

在这个例子中,通过使用" sort( ) "函数将给定的无序列表排序为升序。

例2:

 ```a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( " List in descending order: ", a ) ```. 

输出

在上面的例子中,使用函数" sort( reverse = True ) "对给定的无序列表进行反向排序。

排序算法的时间复杂度

时间复杂度是指计算机运行一个特定算法所需的时间。 它有三种类型的时间复杂度情况。

  • 最坏的情况: 计算机运行程序所需的最大时间。
  • 平均案例: 计算机运行程序所需的最小和最大之间的时间。
  • 最佳案例: 计算机运行程序所需的最小时间。 它是时间复杂性的最佳情况。

复杂度记号

大O记号,O: Big oh符号是表达算法运行时间上限的正式方式。 它被用来衡量最坏情况下的时间复杂度,或者我们说算法完成所需的最大时间量。

大欧米茄记号、 : Big omega符号是传达算法运行时间最低界限的正式方式。 它被用来衡量最佳情况下的时间复杂度,或者我们说算法所花费的优秀时间量。

Theta记号、 : Theta符号是表达两种界限的正式方式,即算法完成所需时间的下限和上限。

Python中的排序方法

泡沫分类

泡沫排序是最简单的数据排序方法,它使用暴力技术。 它将对每个数据元素进行迭代,并与其他元素进行比较,为用户提供排序后的数据。

让我们举个例子来理解这种技术:

  • 我们得到一个元素为 "10, 40, 7, 3, 15 "的数组,现在,我们需要使用Python中的泡沫排序技术将这个数组按升序排列。
    • 第一步是按照给定的顺序排列数组。
    • 在 "迭代1 "中,我们将一个数组的第一个元素与其他元素逐一进行比较。
    • 红色箭头描述的是第一个元素与数组中其他元素的比较。
    • 如果你注意到 "10 "比 "40 "小,所以它仍然在同一位置,但下一个元素 "7 "比 "10 "小,因此它被替换到了第一位置。
    • 上述过程将被反复执行,以对元素进行排序。

    • 在 "迭代2 "中,第二个元素正在与数组的其他元素进行比较。
    • 如果被比较的元素是小的,那么它将被替换,否则它将保持在同一位置。

    • 在 "迭代3 "中,第三个元素正在与数组的其他元素进行比较。

    • 在最后的 "迭代4 "中,倒数第二个元素与数组的其他元素进行比较。
    • 在这一步中,数组被按升序排序。

泡沫分类的程序

 `` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unorted List: " , unsorted_list) print("Sorted List using Bubble SortTechnique: ", Bubble_Sort(unsorted_list)) ````。 

输出

泡沫排序的时间复杂度

  • 最坏的情况: 冒泡排序的最差时间复杂度是O( n 2).
  • 平均案例: 冒泡排序的平均时间复杂度为O( n 2).
  • 最佳案例: 冒泡排序的最佳时间复杂度是O(n)。

优势

  • 它大多被使用,而且很容易实现。
  • 我们可以在不消耗短期存储的情况下交换数据元素。
  • 它需要更少的空间。

劣势

  • 在处理大量的大数据元素时,它的表现并不理想。
  • 它需要 n 对每一个 "n "个数据元素进行排序,需要2个步骤。
  • 它对现实世界的应用并不真正有利。

插入排序

插入式排序是一种简单易行的排序技术,其工作原理类似于扑克牌的排序。 插入式排序通过将每个元素逐一与其他元素进行比较来进行排序。 如果元素大于或小于另一个元素,则将该元素挑出并与另一个元素进行交换。

让我们举个例子

  • 我们得到了一个元素为 "100, 50, 30, 40, 10 "的数组。
  • 首先,我们排列数组并开始比较。
  • 在第一步中,"100 "与第二个元素 "50 "进行比较。"50 "与 "100 "互换,因为它更大。
  • 在第二步中,第二元素 "100 "再次与第三元素 "30 "进行比较并被交换。
  • 现在,如果你注意到 "30 "排在第一位,因为它又比 "50 "小。
  • 比较将一直发生到数组的最后一个元素,在最后,我们将得到排序后的数据。

插入排序的程序

 `` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j>= 0 and key_value <array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i] ) `` ` 

输出

插入排序的时间复杂度

  • 最坏的情况: 插入式排序的最差时间复杂度是O( n 2).
  • 平均案例: 插入式排序的平均时间复杂度为O( n 2).
  • 最佳案例: 插入式排序的最佳时间复杂度是O(n)。

优势

  • 它很简单,易于实施。
  • 它在处理少量数据元素时表现良好。
  • 它不需要更多的空间来实施。

劣势

  • 对大量的数据元素进行分类是没有帮助的。
  • 与其他分拣技术相比,它的表现并不理想。

合并排序

这种排序方法使用分而治之的方法将元素按特定顺序进行排序。 在合并排序的帮助下,元素被分成两半,然后被排序。 在对所有两半进行排序后,元素再次被连接起来,形成一个完美的顺序。

让我们举个例子来理解这个技术

  • 我们得到一个数组 "7,3,40,10,20,15,6,5"。 该数组包含7个元素。 如果我们把它分成一半(0 + 7 / 2 = 3)。
  • 在第二步中,你会看到元素被分为两部分。 每部分有4个元素。
  • 进一步说,这些元素再次被划分,每个元素有2个。
  • 这个过程将持续到数组中只有一个元素为止。 请参考图片中的第4步。
  • 现在,我们将对这些元素进行分类,并开始按照我们的划分来连接它们。
  • 在第5步中,如果你注意到7大于3,那么我们将交换它们并在下一步中加入,反之亦然。
  • 最后,你会注意到,我们的数组正按升序排序。

合并排序的程序

 ``` def MergeSort(arr): if len(arr)> 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i <len(L) and j <len(R): if L[i] <R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i <len(L): arr[k] = L[i] i += 1 k += 1 while j <len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i inrange(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ````。 

输出

合并排序的时间复杂度

  • 最坏的情况: 合并排序的最差时间复杂度是O( n log( n )).
  • 平均案例: 合并排序的平均时间复杂度为O( n log( n )).
  • 最佳案例: 合并排序的最佳时间复杂度是O( n log( n )).

优势

  • 对于这种排序技术,文件大小并不重要。
  • 这种技术适用于一般按顺序访问的数据。 比如说、 链表、磁带机等。

劣势

  • 与其他分拣技术相比,它需要更多空间。
  • 它的效率相对来说比其他的要低。

快速排序

快速排序再次使用分而治之的方法对List或数组中的元素进行排序。 它以枢轴元素为目标,根据选定的枢轴元素对元素进行排序。

比如说

  • 我们得到了一个数组,其元素为 "1,8,3,9,4,5,7"。
  • 让我们假设 " 7 " 是一个试点元素。
  • 现在我们将以这样的方式划分数组,左边包含小于枢轴元素" 7 "的元素,右边包含大于枢轴元素" 7 "的元素。
  • 我们现在有两个数组 " 1,3,4,5 " 和 " 8, 9 " 。
  • 同样,我们必须像上面那样对两个数组进行分割。 唯一的区别是,枢轴元素被改变。
  • 我们需要对数组进行分割,直到得到数组中的单个元素。
  • 最后,按顺序从左到右收集所有的枢轴元素,你将得到排序后的数组。

快速排序的程序

 ``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] <= pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ) return ( i+1 ) def QuickSort( arr, lowest, highest ) : if len( arr ) == 1: return arr if lowest <highest: pi = Array_Partition(arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```` 

输出

快速排序的时间复杂度

  • 最坏的情况: 快速排序的最差时间复杂度是O( n 2).
  • 平均案例: 快速排序的平均时间复杂度为O( n log( n )).
  • 最佳案例: 快速排序的最佳时间复杂度是O( n log( n )).

优势

  • 它被称为Python中最好的排序算法。
  • 在处理大量数据时,它很有用。
  • 它不需要额外的空间。

劣势

  • 其最坏情况下的复杂度与冒泡排序和插入排序的复杂度相似。
  • 当我们已经有了排序后的列表,这种排序方法就没有用了。

堆积排序

堆排序是二进制搜索树的高级版本。 在堆排序中,数组中最大的元素总是放在树的根部,然后,与根部和叶子节点进行比较。

比如说:

  • 我们得到了一个元素为 "40、100、30、50、10 "的数组。
  • " 第1步 " 我们根据数组中元素的存在做了一棵树。

  • 在" 第2步" 我们要做一个最大的堆,即按降序排列元素。 最大的元素将位于顶部(根节点),最小的元素位于底部(叶节点)。 给定的数组成为 "100, 50, 30, 40, 10"。

  • " 第三步 " 通过这样做,我们可以得到最大和最小的元素。

  • " 第四步 " 通过执行同样的步骤,我们得到了排序后的数组。

堆积排序的程序

 `` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left <n and arr[ larger_element ] <arr[ left ]: larger_element = left if right <n and arr[ larger_element ] <arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ) def HeapSortify( arr, n, larger_element )): n = len( arr ) for i in range( n/2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by heap sort: " ) for i in range( n ) : print( arr[ i ] ) ```` 

输出

堆积排序的时间复杂度

  • 最坏的情况: 堆排序的最差时间复杂度是O( n log( n )).
  • 平均案例: Heap排序的平均时间复杂度为O( n log( n )).
  • 最佳案例: 堆排序的最佳时间复杂度是O( n log( n )).

优势

  • 它之所以被使用,主要是因为它的生产力。
  • 它可以作为一种就地的算法来实现。
  • 它不需要大量的存储。

劣势

  • 需要空间来对元素进行分类。
  • 它使元素分类的树。

分拣技术的比较

分拣方法 最佳情况下的时间复杂性 平均案件时间复杂度 最坏情况下的时间复杂性 空间的复杂性 稳定性 在-地方
泡沫排序 O(n) O(n2) O(n2) O(1)
插入式排序 O(n) O(n2) O(n2) O(1)
快速排序 O(n log(n)) O(n log(n)) O(n2) O(N) 没有
合并排序 O(n log(n)) O(n log(n)) O(n log(n)) O(N) 没有
堆积排序 O(n log(n)) O(n log(n)) O(n log(n)) O(1) 没有

在上面的比较表中,"O "是上面解释的大O的符号,而 "n "和 "N "是指输入的大小。

常见问题

问题#1) Python中的sort()是什么?

答案是: 在Python中,sort()是一个用于按特定顺序对列表或数组进行排序的函数。 这个函数简化了在大型项目中进行排序的过程。 它对开发人员非常有帮助。

Q #2) 在Python中如何排序?

答案是: Python提供了各种排序技术,用于对元素进行排序。 比如说、 快速排序、合并排序、气泡排序、插入排序等,所有的排序技术都是高效且易于理解的。

问题#3) Python sort ()是如何工作的?

答案是: sort()函数将给定的数组作为用户的输入,并使用排序算法对其进行特定的排序。 算法的选择取决于用户的选择。 用户可以使用快速排序、合并排序、泡沫排序、插入排序等,这取决于用户的需求。

总结

在上面的教程中,我们讨论了Python中的排序技术,以及一般的排序技术。

  • 泡沫分类
  • 插入排序
  • 快速排序

我们了解了他们的时间复杂性和优点及缺点。 我们还比较了上述所有技术。

滚动到顶部