选择排序(oc/java/Python/scala)
2017-05-26 本文已影响0人
狼牙战士
一、浅谈数组和链表
数组：具有相同类型的元素的集合。数组分配在一块连续的数据空间上，因此存储效率低，插入和删除元素效率低，支持随机访问，访问元素效率高。
链表(单向链表、双向链表、循环链表)：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。插入，删除效率高，空间利用率高，不支持随机访问，查找元素效率低
二、 选择排序介绍：
1.方案一：第一次查找，找出数组中的最小元素，交换至数组第一个位置，第二次查找数组中除了第一个元素，剩下的部分，找出最小元素交换至数组第二个位置，以此类推。。。
2.方案二：第一次查找Array1，找出最小元素，取出来放到一个一开始为空的数组Array2中，并将Array1中的那个最小元素删除，Array1长度减1。第二次查找Array1，找出最小元素，取出来放到一个数组Array2中，并将Array1中的那个最小元素删除。。。。最后Array1长度为0，Array2就是排序后的数组。
方案一：
scala实现代码：
object XuanZe{
def main(args:Array[String]){
var myArray = Array(45, 26, 34, 2, 888, 54, 23, 45, 76, 2);
selectSort(myArray);
for ( x <- myArray ) {
println( x )
}
}
def selectSort(array:Array[Int]):Unit={
var smallest_index:Int = 0;
var temp:Int = 0;
for(i <- 0 to (array.length - 2)){
smallest_index = i;
for(j <- (i+1) to (array.length -1)){
if(array(j)<array(smallest_index)){
smallest_index = j;
}
}
if(smallest_index != i){
temp = array(i);
array(i) = array(smallest_index);
array(smallest_index) = temp;
}
}
}
}
Java实现代码：
import java.util.Arrays;
public class MyClass {
public static void main(String[] args){
int[] sortArray = {45, 26, 34, 2, 888, 54, 23, 45, 76, 2};
selectSort(sortArray);
System.out.println(Arrays.toString(sortArray));
}
private static void selectSort(int[] array){
int smallest_index = 0;
int temp = 0;
for(int i = 0;i<array.length-1;i++){
//无序区的最小数据数组下标
smallest_index = i;
for(int j = i+1;j<array.length;j++){
//在无序区中找到最小数据并保存其数组下标
if(array[j]<array[smallest_index]){
smallest_index = j;
}
}
//如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
if(smallest_index != i){
temp = array[i];
array[i] = array[smallest_index];
array[smallest_index] = temp;
}
}
}
}
OC实现代码：
主文件
#import <Foundation/Foundation.h>
#import "XuanZe.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
XuanZe *xz = [[XuanZe alloc] init];
NSMutableArray* array = (NSMutableArray*)@[@45, @26, @34, @2, @888, @54, @23, @45, @76, @2];
NSLog(@"%@",[xz selectionSort:array]);
}
return 0;
}
实现文件
#import "XuanZe.h"
@implementation XuanZe
-(NSMutableArray*)selectionSort:(NSMutableArray*)array{
int smallest_index = 0;
id temp;
NSMutableArray *arr = [NSMutableArray arrayWithArray:array];
for(int i = 0;i<[arr count];i++){
//无序区的最小数据数组下标
smallest_index = i;
for(int j = i+1;j<[arr count];j++){
//在无序区中找到最小数据并保存其数组下标
if(arr[j]<arr[smallest_index]){
smallest_index = j;
}
}
//如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
if(smallest_index != i){
temp = arr[i];
arr[i] = arr[smallest_index];
arr[smallest_index] = temp;
}
}
return arr;
}
@end
Python实现代码：
def selectionSort(arr):
for i in range(0,len(arr)):
min = i
for j in range(i+1,len(arr)):
if arr[j]<arr[min]:
min = j
arr[i],arr[min] = arr[min],arr[i]
return arr;
print(selectionSort([45,26,34,2,888,54,23,45,76,2]))
方案二：
scala实现代码：
import scala.collection.mutable.ArrayBuffer
object XuanZe1{
def main(args:Array[String]){
var myArray = ArrayBuffer(45, 26, 34, 2, 888, 54, 23, 45, 76, 2);
var myArray1 = selectSort(myArray);
for ( x <- myArray1 ) {
println( x );
}
}
def selectSort(array:ArrayBuffer[Int]):ArrayBuffer[Int]={
var myArrayBuffer = ArrayBuffer(0,0,0,0,0,0,0,0,0,0);
var myArrayBuffer1 = array;
for(i <- 0 to (array.length - 1)){
var smallest_index:Int = findSmallest(myArrayBuffer1);
myArrayBuffer(i) = myArrayBuffer1(smallest_index);
myArrayBuffer1.remove(smallest_index);
}
return myArrayBuffer;
}
def findSmallest(array:ArrayBuffer[Int]):Int={
var smallest:Int = array(0);
var smallest_index:Int = 0;
for(i <- 1 to (array.length - 1)){
if(array(i)<smallest){
smallest = array(i);
smallest_index = i;
}
}
return smallest_index;
}
}
Java实现代码：
import java.util.Arrays;
public class XuanZe {
public static void main(String[] args){
int[] sortArray = {45, 26, 34, 2, 888, 54, 23, 45, 76, 2};
System.out.println("排序结果"+Arrays.toString(selectionSort(sortArray)));
}
private static int[] selectionSort(int[] array){
int[] newArr = new int[10];
int[] array1 = array;
for(int i = 0;i<array.length;i++){
int smallest_index = finSmallest(array1);
newArr[i] = array1[smallest_index];
//去除最小值，数组缩容
array1[smallest_index] = array1[array1.length-1];
array1 = Arrays.copyOf(array1,array1.length-1);
System.out.println(Arrays.toString(array1));
}
return newArr;
}
private static int finSmallest(int[] arr){
//存储最小的值
int smallest = arr[0];
//存储最小值得索引
int smallest_index = 0;
for(int i = 1; i< arr.length;i++){
if(arr[i] < smallest){
smallest = arr[i];
smallest_index = i;
}
}
return smallest_index;
}
}
结果展示:
SYJ.png
OC实现代码：
主文件
#import <Foundation/Foundation.h>
#import "XuanZe.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
XuanZe *xz = [[XuanZe alloc] init];
NSLog(@"%@",[xz selectionSort:(NSMutableArray*)@[@45, @26, @34, @2, @888, @54, @23, @45, @76, @2]]);
}
return 0;
}
XuanZe.m文件
#import "XuanZe.h"
@implementation XuanZe
-(NSMutableArray*)selectionSort:(NSMutableArray*)array{
NSMutableArray *array1 = [[NSMutableArray alloc] initWithArray:array];
NSMutableArray *newArray = [[NSMutableArray alloc] initWithCapacity:0];
for(int i = 0;i<[array count];i++){
int smallest_index = [self findSmallest:array1];
newArray[i] = array1[smallest_index];
//去除最小值
[array1 removeObjectAtIndex:smallest_index];
}
return newArray;
}
-(int)findSmallest:(NSMutableArray*)array{
//存储最小的值
int smallest = (int)array[0];
//存储最小值的索引
int smallest_index = 0;
for(int i = 1; i< [array count];i++){
if((int)array[i] < smallest){
smallest = (int)array[i];
smallest_index = i;
}
}
return smallest_index;
}
@end
结果展示：
SYJ.png
Python实现代码：
def findSmallest(arr):
#存储最小的值
smallest = arr[0]
#存储最小值的索引
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest_index = findSmallest(arr)
#取出数组中最小的元素并将其加入到新的数组中
newArr.append(arr.pop(smallest_index))
return newArr
print(selectionSort([45,26,34,2,888,54,23,45,76,2]))
结果展示：
SYJ.png
