数据结构与算法优化：Java中快速排序和链表操作实例

原创素颜马尾好姑娘i 2024-11-01 15:15 7阅读 0赞

在Java中，快速排序是一种常用的排序算法，它采用分治法（Divide and Conquer）策略来把一个序列分为较小的两个子序列，然后递归地排序两个子序列。链表是一种线性数据结构，其中的元素被存储在称为节点的对象中，每个节点包含数据部分和指向下一个节点的引用（在单向链表中）或指向前一个和后一个节点的引用（在双向链表中）。

下面我将分别给出Java中快速排序和链表操作的简单实例。

###快速排序实例```javapublic class QuickSort {
 public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
 quickSort(arr, low, pi -1);
 quickSort(arr, pi +1, high);
 }
 }

private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low -1);
 for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
 }
 }
int temp = arr[i +1];
arr[i +1] = arr[high];
arr[high] = temp;
 return i +1;
 }

public static void main(String args[]) {
int[] arr = {10,7,8,9,1,5};
int n = arr.length;
 quickSort(arr,0, n -1);
 System.out.println("Sorted array: ");
 for (int i : arr) {
 System.out.print(i + " ");
 }
 }
}
```###链表操作实例####单向链表```javaclass Node {
int data;
Node next;

Node(int d) {
data = d;
 next = null;
 }
}

public class LinkedList {
Node head;// head of the list// Method to insert a new node at the front of the list public void push(int new_data) {
Node new_node = new Node(new_data);
 new_node.next = head;
 head = new_node;
 }

// Method to print the linked list public void printList() {
Node tnode = head;
 while (tnode != null) {
 System.out.print(tnode.data + " ");
tnode = tnode.next;
 }
 }

public static void main(String[] args) {
 LinkedList list = new LinkedList();
 list.push(7);
 list.push(1);
 list.push(3);
 list.push(19);
 System.out.println("Created Linked List: ");
 list.printList();
 }
}
```####链表排序（冒泡排序）

```javapublic class SortedLinkedList {
Node head;// head of the list// Method to insert a new node at the front of the list public void push(int new_data) {
Node new_node = new Node(new_data);
 new_node.next = head;
 head = new_node;
 }

// Method to print the linked list public void printList() {
Node tnode = head;
 while (tnode != null) {
 System.out.print(tnode.data + " ");
tnode = tnode.next;
 }
 }

// Method to sort the linked list public void sort() {
int length = getLength();
 for (int i =0; i < length -1; i++) {
 for (Node node = head; node != null && node.next != null; node = node.next) {
if (node.data > node.next.data) {
int temp = node.data;
 node.data = node.next.data;
 node.next.data = temp;
 }
 }
 }
 }

// Helper method to get the length of the linked list private int getLength() {
int length =0;
Node temp = head;
 while (temp != null) {
 length++;
 temp = temp.next;
 }
 return length;
 }

public static void main(String[] args) {
SortedLinkedList list = new SortedLinkedList();
 list.push(19);
 list.push(3);
 list.push(1);
 list.push(7);
 System.out.println("Original Linked List: ");
 list.printList();
 list.sort();
 System.out.println("Sorted Linked List: ");
 list.printList();
 }
}
```以上代码提供了快速排序和链表